058 K번째 최단경로 찾기

첫번째 코드

 

이번에는 신경써야 하는 것들이 더 생겨서 어렵다...

그리고 heap을 쓴다!

 

코드는 책을 참고했다...

이 문제를 쉽게쉽게 풀 날이 언능 오기를... 답답)

어렵다 다익스트라...

 

import sys
import heapq
input = sys.stdin.readline

n, m, k = map(int, input().split())
distance = [[sys.maxsize] * k for _ in range(n+1)]
A = [[] for _ in range(n+1)]

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

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

while queue:
    cost, node = heapq.heappop(queue)
    for nNode, nCost in A[node]:
        sCost = cost + nCost
        if distance[nNode][k-1] > sCost:
            distance[nNode][k-1] = sCost
            distance[nNode].sort()
            heapq.heappush(queue, [sCost, nNode])

for i in range(1, n+1):
    if distance[i][k-1] == sys.maxsize:
        print(-1)

    else:
        print(distance[i][k-1])

 

통과!

근데 이번에는 다익스트라 앞문제들보다 생각할 것들이 많고 어렵다....

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/1854.%E2%80%85K%EB%B2%88%EC%A7%B8%E2%80%85%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C%E2%80%85%EC%B0%BE%EA%B8%B0

programmers/백준/Platinum/1854. K번째 최단경로 찾기 at main · ornni/programmers