문제

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

# 1240
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n+1):
    graph.append([])
    
for _ in range(n-1):
    u, v, d = map(int, input().split())
    graph[u].append((v, d))
    graph[v].append((u, d))
    
dist = [-1] * (n+1)

def bfs(v):
    global graph, dist
    queue = deque()
    queue.append((v, 0))
    dist[v] = 0
    
    while queue:
        v, time = queue.popleft()
        for g, g_time in graph[v]:
            if dist[g] == -1 or dist[g] > dist[v] + g_time:
                dist[g] = dist[v] + g_time
                queue.append((g, dist[g]))
                
for _ in range(m):
    u, v = map(int, input().split())
    dist = [-1] * (n+1)
    bfs(u)
    
    print(dist[v])

백준 1240 노드사이의 거리