[#알고리즘/최단 경로/[백준]1916번: 최소 비용 구하기(python)]

Question

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

Solution

앞서 구현한 힙을 사용한 다익스트라 알고리즘을 그대로 사용하였다. 다른 점은 모든 노드로 가는 최단 비용(거리)을 출력하는 것이 아닌 도착 노드로 가는데 드는 최단 비용만을 출력한다.

Code

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 도시(노드)의 개수 
n = int(input())
# 버스(간선)의 개수
m = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블
distance = [INF] * (n + 1)

# 모든 간선 정보 입력받기
for _ in range(m) :
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c (튜플로 원소 저장)
    graph[a].append((b, c))
    
    
# 출발 도시, 도착 도시 번호 입력받기
start, end = map(int, input().split())

    
def dijkstra(start) :
    # 우선 순위 큐
    q = []
    # 출발 노드로 가기 위한 최단 경로는 0으로 설정 후 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q :  # 큐가 비어있지 않다면
        # 최단 거리가 가장 짧은 노드 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재(꺼낸) 노드가 이미 처리된 적 있다면 무시
        if distance[now] < dist :
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now] :
            cost = dist + i[1]
            # 현재 노드를 거쳐, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
# 다익스트라 알고리즘 수행
dijkstra(start)

# 도착 도시까지 가는데 드는 최소 비용 출력
print(distance[end])