[백준] 1916 최소비용 구하기 python

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

1916번: 최소비용 구하기

import sys; input = sys.stdin.readline
from heapq import heappop, heappush
inf = 100000000 # 최대값 (max(N)-1) * max(w)
N = int(input()) # 1000
M = int(input()) # 100000
link_list = [list() for _ in range(N + 1)]
for _ in range(M):
    s, e, w = map(int,input().split())
    link_list[s].append((w, e))
    # link_list[e].append((w, s))
s, e = map(int, input().split())

dist = [inf for _ in range(N + 1)]
visit = [False for _ in range(N + 1)]
dist[s] = 0
q = [(0, s)]
while q:
    w, cur = heappop(q)
    if visit[cur]: continue
    visit[cur] = True
    for adj_w, adj in link_list[cur]:
        if dist[adj] > adj_w + w:
            dist[adj] = adj_w + w
            heappush(q,(dist[adj], adj))

print(dist[e])

최소비용을 구해야하는 문제인데 시작과 끝점이 지정되어있으므로 다익스트라를 사용해서 풀면된다.

이전에 풀었던 문제인데 재채점이 되어서 다시 풀었다