[파이썬]백준 1916 최소비용구하기

링크

백준 1916 최소비용구하기

다익스트라를 구현하면 되는 문제

처음에 틀렸다고 해서 아니 도대체 왜틀렸지 했는데 dis를 0xffffff로 줘서 틀렸었다. 그래서 문제를 보고 만들 수 있는 최댓값으로 바꿔줬다.

저번에 문제 풀 때 유향그래프에선 굳이 visit을 할 필요 없다는 점이 생각나서 그점을 활용했다.

정답 코드

import sys; input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(start, end):
    dis = [100000000] * (N + 1)
    dis[start] = 0
    q = [[0, start]]
    while q:
        k, u = heappop(q)
        if k > dis[u]: continue
        for w, v in G[u]:
            if dis[v] > w + dis[u]:
                dis[v] = w + dis[u]
                heappush(q, [dis[v], v])

    return dis[end]

N = int(input())
M = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = map(int, input().split())
    G[u].append([w, v])
start, end = map(int, input().split())

print(dijkstra(start, end))

알게된 것👨‍💻

• 다익스트라에서 inf는 충분히 큰 숫자로 줄 것