_다익스트라 알고리즘은
https://velog.io/@galong/다익스트라Dijkstra-알고리즘-백준-1753번/

여기 글에 작성하여 생략하겠습니다!

여기에서는 우선순위 큐를 사용합니다.
우선순위 설명도
https://velog.io/@galong/알고리즘-우선순위-큐/
여기에서 확인하실 수 있습니다 :)

---

K번째 최단 경로 찾기 - 백준 1854번

https://www.acmicpc.net/problem/1854

풀이

이전과는 다르게 k번째 거리를 구해야한다. 즉, 최단 거리를 구할 때는 visited로 이전 방문 노드를 기록해놨었지만, k번째 거리를 구하려면 방문 했던 곳을 또 방문을 해서 거리를 비교해야한다.
결론 visited를 기록할 필요가 없다!
또한 k개의 거리를 저장할 distance를 선언해야 한다.

그리고 우선순위 큐를 사용할 것이다.

우선순위 큐로 선언하면 편리한점
다익스트라 알고리즘 수행을 위한 노드 데이터를 저장하는 객체 형식을 우선순위 큐로 선언했기 때문에 새로운 노드가 삽입됐을 때 별도의 정렬을 해주지 않아도 자동으로 정렬돼 편리하게 구현할 수 있다는 장점이 있습니다.

초기 설정

• direction
• distance
• pq

direction
경로와 시간을 저장

direction = [[] for _ in range(n + 1)]
for _ in range(m):
    start, end, time = map(int, input().split())

    direction[start].append([end, time])
    
#결과
# 1  ->  [[2, 2], [3, 7], [4, 5], [5, 6]]
# 2  ->  [[4, 2], [3, 4]]
# 3  ->  [[4, 6], [5, 8]]
# 4  ->  []
# 5  ->  [[2, 4], [4, 1]]

distance
k 개의 row를 갖는 2차원 리스트 형태

distance = [[sys.maxsize] * k for _ in range(n + 1)]
distance[1][0] = 0

# 결과
# 1  ->  0 9223372036854775807 
# 2  ->  9223372036854775807 9223372036854775807 
# 3  ->  9223372036854775807 9223372036854775807 
# 4  ->  9223372036854775807 9223372036854775807 
# 5  ->  9223372036854775807 9223372036854775807 

pq
(현재 노드의 거리) + (다음 노드까지의 거리) < (다음 노드의 distance) 갱신

pq = [(0, 1)]

다익스트라 수행

while pq:
    cost, node = heapq.heappop(pq)
    
    for nextNode, nextCost in direction[node]:
        sumCost = cost + nextCost

        if distance[nextNode][k - 1] > sumCost:
            distance[nextNode][k - 1] = sumCost
            distance[nextNode].sort()

            heapq.heappush(pq, [sumCost, nextNode])

흐름
= 1 =

• 힙 큐 = [[0,1]]
• pq에서 pop한 노드 = 1
• cost = 0
• pop한 뒤, 힙 큐 = []

distance

node	[0]	[1]
1	0	∞
2	2	∞
3	7	∞
4	5	∞
5	6	∞

= 2 =

• 힙 큐 = [[2,2], [5, 4], [6, 5], [7, 3]]
• pq에서 pop한 node = 2
• cost = 2
• pop한 뒤, 힙 큐 = [[5, 4], [6, 5], [7, 3]]

distance

node	[0]	[1]
1	0	∞
2	2	∞
3	6	7
4	4	5
5	6	∞

1. direction[2] 중에서 nextNode = 4, nextCost = 2인 경우,
   5(distance[4][1]) > 2(cost) + 2(nextCost) 이므로 distance[4][1] = 4으로 변경하고 distance[4]를 정렬한다.

2. direction[2] 중에서 nextNode = 3, nextCost = 4인 경우,
   7(distance[3][1]) > 2(cost) + 4(nextCost) 이므로 distance[3][1] = 6으로 변경하고 distance[3]을 정렬한다.

= 3 =

• 힙 큐 = [[4, 4], [5, 4], [6, 3], [7, 3], [6, 5]]
• pq에서 pop한 node = 4
• cost = 4
• pop한 뒤, 힙 큐 = [[5, 4], [6, 3], [7, 3], [6, 5]]

갱신 x

... 반복

전체 코드

# 다익스트라
import sys
import heapq  # 우선순위 큐

input = sys.stdin.readline
n, m, k = map(int, input().split())

direction = [[] for _ in range(n + 1)]
distance = [[sys.maxsize] * k for _ in range(n + 1)]

for _ in range(m):
    start, end, time = map(int, input().split())

    direction[start].append([end, time])

distance[1][0] = 0
pq = [(0, 1)]

while pq:
    cost, node = heapq.heappop(pq)
    
    for nextNode, nextCost in direction[node]:
        sumCost = cost + nextCost

        if distance[nextNode][k - 1] > sumCost:
            distance[nextNode][k - 1] = sumCost
            distance[nextNode].sort()

            heapq.heappush(pq, [sumCost, nextNode])


for dis in distance[1:]:
    if dis[k - 1] == sys.maxsize:
        print(-1)
    else:
        print(dis[k - 1])