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

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
N = int(input())
M = int(input())
link_arr = [list() for _ in range(N + 1)]
for _ in range(M):
    st, en, we = map(int, input().split())
    link_arr[st].append((en, we))

# dijkstra
start, end = map(int, input().split())
inf = 10 ** 10
visit = [0] * (N + 1)
dist = [inf] * (N + 1)
q = [(0, start)]
dist[start] = 0
while q:
    w, cur = heappop(q)
    visit[cur] = 1
    for adj_node, adj_w in link_arr[cur]:
        if not visit[adj_node] and dist[adj_node] > dist[cur] + adj_w:
            dist[adj_node] = dist[cur] + adj_w
            heappush(q, (dist[adj_node], adj_node))
print(dist[end])

다익스트라로 문제풀었다

문제를 잘 봐야하는게 단방향인지 양방향인지 제대로 안봐서 틀렸었다...

나머지는 쉽게 구현했다.