[백준/Python] 1916. 최소비용 구하기

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

 

📌  문제 접근

문제를 보자마자 며칠 전에 푼 택배 배송이 떠올랐다.

 

도시의 개수 N과 버스 노선 M이 주어지고, 각 버스 노선은 출발 도시, 도착 도시, 비용으로 표현된다. 목표는 특정 시작 도시에서 도착 도시까지 드는 최소 비용을 구하는 것이다.

 

즉, 다익스트라를 이용한 최단 거리 문제로 풀 수 있다.

---

🔍 문제 풀이

import heapq

N = int(input())  # 도시 개수
M = int(input())  # 버스 노선 개수

# 인접 리스트 그래프
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    s, e, cost = map(int, input().split())
    graph[s].append((e, cost))  # 방향 그래프 (s -> e)

start, end = map(int, input().split())

# 다익스트라 거리 배열
dist = [float('inf')] * (N + 1)
dist[start] = 0

# 우선순위 큐 (현재까지 비용, 정점)
pq = [(0, start)]

while pq:
    distance, node = heapq.heappop(pq)

    # 이미 더 짧은 경로가 있으면 스킵
    if distance > dist[node]:
        continue

    # 인접한 노드 확인
    for next, w in graph[node]:
        if dist[next] > dist[node] + w:
            dist[next] = dist[node] + w
            heapq.heappush(pq, (dist[next], next))

print(dist[end])