Ch9.최단 경로 - 전보

[ 접근 방법 ]

전형적인 다익스트라 알고리즘 문제이다.

책의 학습내용을 토대로 다익스트라 알고리즘을 구현한다. 

[ 작성 코드 ]

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

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

distance = [INF] * (n + 1)

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

for i in range (m):
    a, b, c = map(int , input().split() )
    graph[a].append((b,c))
    
def dijkstra(c):
    q = []
    distance[c] = 0
    heapq.heappush(q,(0,c))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            if distance[i[0]] > dist + i[1]:
                distance[i[0]] = dist + i[1]
                heapq.heappush(dist + i[1],i[0])