[백준 #1916]: 최소 비용 구하기(python)

백준#1916:최소 비용 구하기

from sys import maxsize
import sys
import heapq

node_index = int(sys.stdin.readline())
line_index = int(sys.stdin.readline())
graph = [[] for i in range(node_index + 1)]
for _ in range(line_index):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
start_index,end_index  = map(int,sys.stdin.readline().strip().split())  
distance = [maxsize] * (node_index + 1)

def dijkstra(start_index):
    q = []
    heapq.heappush(q, (0, start_index))
    distance[start_index] = 0
    while q:  
        dist, now = heapq.heappop(q)
        if (now == end_index):
            print(dist)
            exit()
        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_index)

해당문제는 다익스트라 알고리즘을 활용하면 굉장히 쉽게 풀린다. 중요한 포인트는 효율을 위해 내가 원하는 도시에 최단경로가 확정이 났을경우 출력시켜주고 프로그램을 종료시켜준다.