백준 1916 최소비용 구하기 python

Concept

heap을 이용한 다익스트라 구현
교과서대로의, 구현이다
사실 올해 초 까지만 해도 다익스트라 구현이 익숙하지 않았는데 지금은 할 만한 걸 보니
성장했?나? 싶긴 하다

다들 알겠지만 뭐... Greedy를 이용한 그래프 문제... 그것이 다익스트라...
해당 정점에서 인접 정점을 탐색하고 거리를 갱신하고... 그렇게 푸는... 문제...

Code

import heapq

def dijkstra(start_v):
    q = []
    distance[start_v] = 0
    heapq.heappush(q, (0, start_v))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next_node in graph[now]:
            cost = dist + next_node[1]
            if cost < distance[next_node[0]]:
                distance[next_node[0]] = cost
                heapq.heappush(q, (cost, next_node[0]))

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [int(1e9) for _ in range(n + 1)]
for _ in range(m):
    s, e, w = map(int, input().split())
    graph[s].append((e, w))
st, en = map(int, input().split())

dijkstra(st)
print(distance[en])