BOJ 1916 최소비용 구하기 Python3

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

 

 

 

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
N = int(input().rstrip())
M = int(input().rstrip())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    s, e, w = map(int, input().rstrip().split())
    graph[s].append((e, w))
start, end = map(int, input().rstrip().split())

distance = [INF] * (N+1)
distance[start] = 0

def dijkstra():
    q = []
    heapq.heappush(q, (0, start))
    while q:
        weight, now = heapq.heappop(q)

        if distance[now] < weight:
            continue

        for ce, cw in graph[now]:
            cost = weight + cw
            if cost < distance[ce]:
                distance[ce] = cost
                heapq.heappush(q, (cost, ce))

dijkstra()
print(distance[end])