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

택배 배송가는데 가는 길에 소한테 여물 바쳐야돼서 손실 최소한으로 갈 때 비용 찾는 문제이다.
다익스트라를 써야했는데 매번 어떻게 쓰는지 까먹어서 예전 코드 참고해서 해결했다.

Python

from heapq import heappush, heappop
from collections import defaultdict

n, m = map(int, input().split())

edges = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())

    edges[a].append((c, b))
    edges[b].append((c, a))

que = [(0, 1)]

dist = [50000 * 50000] * (n + 1)
dist[1] = 0

while que:
    cost, now = heappop(que)

    if dist[now] >= cost:
        for nc, next in edges[now]:
            if cost + nc < dist[next]:
                dist[next] = cost + nc
                heappush(que, (dist[next], next))

print(dist[-1])

각 위치에 대해서 갈 수 있는 위치와 비용을 딕셔너리로 저장했다.
BFS와 비슷하게 que에 최초 비용 0과 시작지점 1을 세팅하고, visited 대신에 dist를 활용해서 1부터 다른 위치까지 갈 수 있는 거리를 저장하게 했다. 초기화는 위치의 개수 5만 * 최대 거리 5만으로 했다.

시작지점의 dist는 0으로 초기화하고, que에서 heappop으로 비용이 최소인 곳을 꺼냈다.
만약 뽑은 비용이 지금 저장된 비용(dist)보다 작거나 같다면 업데이트를 진행햇다.
다음 노드를 탐색하면서 다음노드의 비용과 현재비용을 비교하면서 더 작은 쪽을 저장하도록했고 업데이트 된 경우에 que에 추가해주었다.

그리고 모든 탐색이 끝나면 dist[n]을 출력했다.