알고리즘: 백준 1753번 최단경로 (feat.python)

 

1753번: 최단경로

 

import sys
import heapq
read = sys.stdin.readline
N = int(read())
M = int(read())
graph = {i:[] for i in range(1, N+1)}
for i in range(1, M+1):
    s, e, v = map(int, read().split())
    graph[s].append([e,v])
start, end = map(int, read().split())
INF = sys.maxsize
dist = [0] + [INF for _ in range(N)]
dist[start] = 0
hq = list()
heapq.heappush(hq, [0, start])
while hq:
    current_weight, current_node = heapq.heappop(hq)
    for near_node, near_weight in graph[current_node]:
        next_weight = near_weight + current_weight
        if next_weight < dist[near_node]:
            dist[near_node] = next_weight
            heapq.heappush(hq, [dist[near_node], near_node])
print(dist[end])