Koala - 13기/코딩테스트 준비 스터디

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

Langerak 2024. 2. 24. 16:21

문제

풀이

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()