백준 1240번: 노드사이의 거리 (다익스트라)

백준 1240번: 노드사이의 거리
가장 짧은 거리를 구하려고 플로이드 워셜로 풀었는데, O(n^3)이라 시간초과가 난다.

플로이드워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구할 때, 다익스트라는 한 지점에서 다른 특정 지점까지의 최단 경로를 구할 때 사용한다.

다익스트라로 구하는 a와 b 사이의 최단 경로
① a와 이어진 노드와 a의 거리 저장
② 그 노드에서 이어진 다른 노드와 a의 거리 계산
③ 저장된 경로보다 짧으면 갱신하고 거기서 이어지는 경로들 탐색

짧은 경로부터 찾으면 좋으니까 heap을 쓴다보다

import heapq as hq
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
edge = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b, d = map(int, input().split())
    edge[a].append((b, d))
    edge[b].append((a, d))

for i in range(m):
    distance = [10000 * 1000] * (n + 1)
    a, b = map(int, input().split())
    heap = [(a, 0)]
    distance[a] = 0
    while heap:
        cur_n, d = hq.heappop(heap)
        if distance[cur_n] < d:
            continue
        for next_n, next_d in edge[cur_n]:
            next_d += d
            if next_d < distance[next_n]:
                distance[next_n] = next_d
                hq.heappush(heap, (next_n, next_d))
    print(distance[b])