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

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

이번 문제는 다익스트라 알고리즘으로 해결하는 문제이다.
문제 이름 그대로 k번째 최단 경로를 구해주면 된다.
처음엔 너무 쉽게 생각하고 뚝딱거리다가 몇번을 삽질하고 한참을 고민했었다.

결국엔 다른분의 코드를 한번 읽어보고 다시 풀었는데
힌트는 2중리스트에 최단경로를 저장하고 오름차순으로 정렬을 해줘서 그 다음 최단경로를 다시 저장하는 방식이었다. 다른분들은 우선순위 큐에 저장하는 방식도 많이 썼던데 처음 이해했던 방식으로 풀어서 제출하였다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

n, m, k = map(int, input().split())
graph =[[] for _ in range(n + 1)]
dp = [[inf] * k for _ in range(n + 1)]
heap = []

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

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

dijkstra(1)

print(dp)
for i in range(1, n + 1):
    if dp[i][k-1] == inf:
        print(-1)
    else:
        print(dp[i][k-1])