[Python] 백준 5972번 택배 배송

문제

5972번: 택배 배송

입력

• 첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.
• 둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

• 첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

입력 예제

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

출력 예제

5

문제 풀이

• 전형적인 다익스트라 알고리즘 문제
• 최소 여물이 있는 경로로 갱신해가며 이동한 후, 각 값을 갱신 해 놓은 distance 리스트에서 n번째 값을 출력

코드

import heapq
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
INF = int(1e9)
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
    # 양방향
    a,b,c = map(int,input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(1)
print(distance[n])