[백준] 1916번 - 최소비용 구하기

---

문제 분석

시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 다익스트라 알고리즘을 통해 해결 할 수 있다.

---

소스 코드

# 최소비용 구하기

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
arr = [[] for _ in range(N + 1)]
minRoute = [sys.maxsize] * (N + 1)
visited = [False for _ in range(N + 1)]

for _ in range(M):
    start, end, value = map(int, input().split())
    arr[start].append((end, value))

startNode, endNode = map(int, input().split())
minRoute[startNode] = 0

queue = PriorityQueue()
queue.put((0, startNode))

while not queue.empty():
    routeValue, nextNode = queue.get()
    if visited[nextNode]:
        continue
    visited[nextNode] = True

    for v in arr[nextNode]:
        minRoute[v[0]] = min(minRoute[v[0]], minRoute[nextNode] + v[1])
        queue.put((minRoute[v[0]], v[0]))

print(minRoute[endNode])