백준 1240. 노드사이의 거리

https://www.acmicpc.net/problem/1240

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int,input().split())
arr = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b,dist = map(int,input().split())
    arr[a].append((b, dist))
    arr[b].append((a, dist)) # 무방향이므로 양쪽으로 연결

def bfs(start, end):
    q = deque([(start, 0)])
    visited = [0] * (N + 1)
    visited[start] = 1

    while q:
        node, total_dist = q.popleft()

        if node == end:
            return total_dist

        for nxt, dist in arr[node]:
            if not visited[nxt]:
                visited[nxt] = 1
                q.append((nxt, total_dist + dist))

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

- 노드 사이의 관계(거리)를 구하는 문제이므로 BFS 사용!