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

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

1916번: 최소비용 구하기

 

어제 푼 다익스트라 코드 이용해서 조금만 손 봤더니 그냥 풀렸다..

다익스트라 코드 외우면 이 문제 저 문제 풀기 수월하겠네. 외워야겠다.

 

시작점, 도착점만 입력 받아서 다익스트라 이용해서 dist 배열 구하고 변수(cost) 에 저장한 다음,

해당 배열의 도착점 인덱스 값을 출력해주면 된다. (cost[end])

 

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    q = []
    dist = [float('inf') for i in range(n+1)]
    heapq.heappush(q, (0, start)) #(dist, current)
    dist[start] = 0

    while q:
        distance, current = heapq.heappop(q)
        if distance > dist[current]:
            continue
        for i_end, i_cost in graph[current]:
            new_dist = distance + i_cost
            if new_dist < dist[i_end]:
                dist[i_end] = new_dist
                heapq.heappush(q, (new_dist, i_end))
    return dist

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split()) #a: 출발, b: 도착, c: 비용
    graph[a].append([b, c])
start, end = map(int, input().split())
cost = dijkstra(start)
print(cost[end])