[백준] 5972번 택배 배송(파이썬)

난이도: GOLD IV

문제해결 아이디어

• 기본적인 다익스트라 문제이다

import sys
import heapq


input = sys.stdin.readline

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

INF = int(1e9)

distance = [INF] * (n+1)

graph = [[] for _ in range(n+1)]

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

h = [(0,1)]

distance[1] = 0

while h:
    dist, now = heapq.heappop(h)

    if distance[now] < dist:
        continue

    for next,cost in graph[now]:
        if distance[next] > cost + dist:
            distance[next] = cost + dist
            heapq.heappush(h,(cost+dist, next))

print(distance[n])