[1916] 최소비용 구하기

예시 데이터 상황

• 노드 수(N): 5개 / 간선 수(M): 8개
• 시작점: 1번 / 도착점: 5번
• 초기 상태: dists = [0, inf, inf, inf, inf, inf] (1번 노드만 0)

---

단계별 동작 과정

1. 시작 단계 (노드 1)

우선순위 큐에서 (0, 1)을 꺼냄. 1번 노드와 연결된 인접 노드들을 확인하여 거리를 갱신함.

• 1 → 2: 비용 2 (0+2 < inf) → dists[2] = 2
• 1 → 3: 비용 3 (0+3 < inf) → dists[3] = 3
• 1 → 4: 비용 1 (0+1 < inf) → dists[4] = 1
• 1 → 5: 비용 10 (0+10 < inf) → dists[5] = 10
• 큐 상태: [(1, 4), (2, 2), (3, 3), (10, 5)] (비용 순 정렬)

2. 최단 거리 노드 선택 (노드 4)

큐에서 가장 비용이 적은 (1, 4)를 꺼냄. 4번 노드를 거쳐 갈 수 있는 경로를 확인함.

• 4 → 5: 비용 1(현재) + 3(가중치) = 4. 기존 dists[5]인 10보다 작으므로 갱신.
• 결과: dists[5] = 4
• 큐 상태: [(2, 2), (3, 3), (4, 5), (10, 5)]

3. 다음 최단 거리 선택 (노드 2)

큐에서 (2, 2)를 꺼냄. 2번 노드와 연결된 경로 확인.

• 2 → 4: 비용 2 + 2 = 4. 현재 dists[4]는 1이므로 갱신하지 않음 (Pass).
• 큐 상태: [(3, 3), (4, 5), (10, 5)]

4. 경로 확장 (노드 3)

큐에서 (3, 3)을 꺼냄. 3번 노드와 연결된 경로 확인.

• 3 → 4: 비용 3 + 1 = 4. 현재 dists[4]는 1이므로 갱신 안 함.
• 3 → 5: 비용 3 + 1 = 4. 현재 dists[5]가 4이므로 갱신 안 함 (이미 최단 거리 발견).
• 큐 상태: [(4, 5), (10, 5)]

5. 목적지 확정 (노드 5)

큐에서 (4, 5)를 꺼냄. 이미 dists[5]가 4이므로 방문 처리됨. 그 뒤에 남아있던 (10, 5)는 if dists[cur] < dist: 조건에 의해 무시됨.

---

최종 결과

• 최종 거리 테이블: [0, 0, 2, 3, 1, 4] (1번부터 5번까지 순서대로)
• 1번에서 5번까지의 최소 비용: 4

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
city = [[] for _ in range(N + 1)]

for _ in range(M):
    s, e, c = map(int, input().strip().split())
    city[s].append((e, c))

sn, en = map(int, input().strip().split())


def digk(start):
    dists = [sys.maxsize for _ in range(N + 1)]

    dists[start] = 0
    q = []
    # (비용, 노드)
    heapq.heappush(q, (0, start))

    while q:
        # 현재 가장 짧은 거리 노드 추출
        dist, cur = heapq.heappop(q)
        # 이미 방문 or 최단거리가 아니면 스킵
        if dists[cur] < dist:
            continue
        # 인접 노드 확인
        for next, weight in city[cur]:
            cost = dist + weight
            if cost < dists[next]:
                dists[next] = cost
                heapq.heappush(q, (cost, next))
    return dists


result = digk(sn)
print(result[en])