[백준/Python] 5972번 택배 배송

문제

풀이

1부터 N까지의 노드가 있고, 1에서 N까지 가는 최단 거리를 찾는 문제와 동일하다.

다익스트라를 사용하여 최단 거리를 구해주었다.

코드

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
INF = 1e9

def dijkstra(graph, n):
    hq = [(0, 1)]
    distance = [1e9] * (n + 1)
    distance[1] = 0

    while hq:
        dist, cur = heappop(hq)
        if dist > distance[cur]:
            continue  # 예외 처리
        for weight, next_node in graph[cur]:
            next_dist = dist + weight
            if next_dist < distance[next_node]:
                distance[next_node] = next_dist
                heappush(hq, (next_dist, next_node))
    print(distance[n])

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        s, e, w = map(int, input().split())
        graph[s].append((w, e))
        graph[e].append((w, s))
    dijkstra(graph, n)

if __name__ == "__main__":
    main()