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

리뷰

출력에서 예제 테스트용인 인덱스 5를 넣었다가 한번 틀려버렸다 ㅠ

 

문제 풀이

1. n, m값을 받아주고 e는 빈 리스트를 n + 1개, dist는 INF 를 n + 1개로 초기화 해준다.
2. m개 줄에 a, b, c를 받아주고 a번 노드에 거리 c와 도착지점 b를 리스트로 추가해 준다.
3. start와 end가 될 도시의 정보를 받아와 주고 힙에 [0, start]를, start 도시의 거리를 0으로 초기화 해준다.
4. while루프를 시작하여 현재 누적 거리보다 더 빠른 거리가 있을 경우 해당 도시까지의 거리를 최신화 해준다.
5. while루프를 마친 후 end 도시까지의 거리를 dist[end]를 통해 출력해 준다.

 

참고 사항

마지막줄에 시작 도시와 도착 도시의 정보가 있으니 꼭 참고하자

 

 

정답 코드

import sys
import heapq

INF = sys.maxsize
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
e = [[] for _ in range(n + 1)]
dist = [INF] * (n + 1)
for _ in range(m):
    a, b, c, = map(int, sys.stdin.readline().split())
    e[a].append([c, b])
start, end = map(int, sys.stdin.readline().split())
heap = [[0, start]]
dist[start] = 0
while heap:
    cd, cn = heapq.heappop(heap)
    if dist[cn] != cd: continue
    for nd, nn in e[cn]:
        if dist[nn] > cd + nd:
            dist[nn] = cd + nd
            heapq.heappush(heap, [dist[nn], nn])
print(dist[end])