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

문제

1916번: 최소비용 구하기

입력

• 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
• 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

• 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

입력 예제

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

출력 예제

4

문제 풀이

• 연결되어 있는 노드까지 도달하는 최단 경로를 탐색한 후, 목적지노드의 거리비용을 출력한다.

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

# 간선정보 입력받기
for _ in range(m):
    #출발, 도착, 비용
    a,b,c = map(int,input().split())
    graph[a].append((b, c))

#출발노드와 도착노드
start, end = map(int,input().split())

def dijkstra(start, end):
    q = []
    # 비용, 노드순으로 힙에 넣기
    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]))
    return distance[end]

print(dijkstra(start, end))