[백준] 1916번-(Python 파이썬) - Dijkstra

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

다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 처음엔 최단경로 알고리즘을 왜 다익스트라라고 부를까라고 궁금점이 생겨 찾아보니 처음 고안한 사람의 이름을 따온거였다

문제풀이
1.출발 지점에서 도착 지점으로 가는 단방향 그래프 만들기
2.그래프에서 출발점에서 도착점으로 연결된 점을 이동해준다.
2-1.출발점에서 도착점까지 최단거리로 이동는데 드는 비용을 dp에 저장한다.
2-2.dp[이동할 점]이 (현재 가중치 + 이동 비용) 보다 크면, 값을 (현재가중치 + 이동 비용)으로 바꿔준다.
dp[이동할 점]의 값을 출력한다.

처음 공부할 때 그래프는 만들었는데 어떻게 최소값으로 찾아갈지 막막했었는데 heapq를 이용하니 간단하게 해결되었다!

코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
dp = [inf] * (n + 1)
heap = []

for _ in range(m):
    d, a, v = map(int, input().split())
    graph[d].append([a, v])

d_c, a_c = map(int, input().split())

def dijkstra(start):
    dp[start] = 0
    heappush(heap, [0, start])
    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

dijkstra(d_c)
print(dp[a_c])