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

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

1916번: 최소비용 구하기

2023.04.11 - [코딩 테스트/개념] - Dijkstra algorithm

# 1 <= N <= 1000
# 1 <= M <= 100000
# positive weight, start node

import sys
from queue import PriorityQueue

readline = sys.stdin.readline

N = int(readline())
M = int(readline())

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    v1, v2, w = map(int, readline().split())
    graph[v1].append((v2, w))
    
start, end = map(int, readline().split())

infinity = sys.maxsize
distances = [infinity for _ in range(N + 1)]
distances[start] = 0

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

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

while queue.qsize() > 0:
    d, v = queue.get()
    
    if visited[v]:
        continue
    visited[v] = True
    
    for (adj_v, w) in graph[v]:
        distances[adj_v] = min(distances[adj_v], d + w)
        queue.put((distances[adj_v], adj_v))
        
print(distances[end])

시작 노드부터 특정 노드까지의 최소 거리를 구하는 문제고, 양수의 가중치이므로 다익스트라 알고리즘을 활용하면 된다.