BOJ - 1854 - K번째 최단경로 찾기

import sys
from heapq import heappush, heappop

def Dijkstra(K, graph, V):
    heap = []
    distance = [[] for _ in range(V+1)]
    distance[1].append(0)
    heappush(heap, (0, 1))

    while heap:
        weight, location = heappop(heap)
        for l, w in graph[location]:
            distance[l].sort()
            if len(distance[l]) < K:
                distance[l].append(weight + w)
                heappush(heap, (weight + w, l))
            elif distance[l][-1] > weight + w:
                distance[l].pop()
                distance[l].append(weight + w)
                heappush(heap, (weight + w, l))

    for d in range(1, V+1):
        print(-1 if len(distance[d]) < K else max(distance[d]))

def solution():
    V, E, K = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(V + 1)]

    for _ in range(E):
        u, v, w = map(int, sys.stdin.readline().split())
        graph[u].append([v, w])

    Dijkstra(K, graph, V)

solution()

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