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

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

1916번: 최소비용 구하기

---

풀이 과정

N개의 도시, M개의 버스가 주어지고 버스의 출발점과 도착지점, 그리고 드는 버스 비용이 주어질 때, A번째 도시에서 B번째 도시로 가는 경로의 최소 버스 비용을 구하는 문제이다.

 

https://greentea31.tistory.com/205

LeetCode - 743. Network Delay Time [Python]

이 문제와 비슷한 조건의 문제이다. 똑같이 다익스트라 알고리즘을 구현해서 문제를 해결할 수 있다.

 

---

소스 코드

import sys
import heapq
import collections

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = collections.defaultdict(list)
dist = collections.defaultdict(int)

for _ in range(M):
    depart, arrive, cost = map(int, sys.stdin.readline().split())
    graph[depart].append((cost, arrive))

start, end = map(int, sys.stdin.readline().split())

Q = [[0, start]]

while Q:
    cost, node = heapq.heappop(Q)
    if node not in dist:
        dist[node] = cost
        for w, v in graph[node]:
            temp = cost + w
            heapq.heappush(Q, [temp, v])

print(dist[end])