다익스트라 알고리즘 아카이빙

import heapq
import sys
input = sys.stdin.readline
INF = sys.maxsize

node = 0 #노드 개수
line = 0 #간선 개수
graph = [[] for i in range(node + 1)] #graph[a]에 b로 가는 간선과 비용 (b, c) 담기
dist = [INF] * (node + 1) #최단거리 테이블

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) #시작 노드는 비용 0
    dist[start] = 0
    while q:
        cost, now = heapq.heappop(q)
        if dist[now] < cost:
            continue
        for i in graph[now]: #현재와 인접한 노드들 확인
            next = cost + i[1]
            if next < dist[i[0]]:
                dist[i[0]] = next
                heapq.heappush(q, (next, i[0]))

dijkstra(0)