1916 - 최소비용 구하기

ggodong.tistory.com/268

1753 - 최단경로

해당 문제랑 완전 같은 문제입니다.

 

그래서 뭐 딱히 설명은 필요없을거 같고요.

 

import sys
import heapq

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

costs = [[] for _ in range(N + 1)]

for _ in range(M):
    s, e, c = map(int, sys.stdin.readline().split())
    costs[s].append((e, c))

S, E = map(int, sys.stdin.readline().split())

pq = []
INF = float('inf')

visited = [INF for _ in range(N + 1)]

heapq.heappush(pq, [0, S])
visited[S] = 0

while pq:
    cost, node = heapq.heappop(pq)
    for arr in costs[node]:
        nxtnode, nxtcost = arr
        if visited[nxtnode] > nxtcost + cost:
            visited[nxtnode] = nxtcost + cost
            heapq.heappush(pq, [nxtcost + cost, nxtnode])

print(visited[E])

코드만 올리도록 할게요 ~

---

이상 1916 - 최소비용 구하기였습니다. ^_^