[백준/Python] Gold V #1240 노드사이의 거리

1240번: 노드사이의 거리

문제

N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

풀이

from collections import deque

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int,input().split())
  graph[a].append([b,c])
  graph[b].append([a,c])

def bfs(start, end):
  queue = deque()
  queue.append((start, 0))
  visited = [False] * (n+1)
  visited[start] = True
  while queue:
    v, d = queue.popleft()
    if v == end: return d
    for i, l in graph[v]:
      if not visited[i]:
        visited[i] = True
        queue.append((i, d+l))

for _ in range(m):
  a, b = map(int,input().split())
  print(bfs(a,b))