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

n개의 노드와 n-1개의 간선이 있는 그래프에서 특정 두 노드 사이의 거리를 측정하고 싶은 문제이다.

BFS로 해결할 수 있었다.

Python

from collections import defaultdict

n, m = map(int, input().split())

tree = defaultdict(list)

for _ in range(n-1):
  a, b, c = map(int, input().split())
  
  tree[a].append((b, c))
  tree[b].append((a, c))
for _ in range(m):
  a, b = map(int, input().split())
  que = [(a, 0)]
  idx = 0
  visited = [True] * (n+1)
  visited[a] = False
  
  ans = []
  
  while idx < len(que):
    now, cost = que[idx]
    idx += 1
    
    if now == b:
      ans.append(cost)
    
    for next, c in tree[now]:
      if visited[next]:
        que.append((next, cost + c))
        visited[next] = False
  print(min(ans))

tree라는 딕셔너리를 생성하고 이것을 이용해서 인접리스트를 만들었다. 그리고 확인하고 싶은 노드 수 m만큼 돌면서 두 노드를 입력받고, 그 중 하나를 시작으로 BFS를 했다.
탐색하면서 만약 다른 노드를 만난다면 해당 cost를 ans라는 리스트에 추가해주었고, 마지막으로 가장 짧은 거리의 cost를 출력하였다.