heapq구조를 이용하여 풀었습니다.

근데 heapq 대신에 deque 을 사용하였더니 시간초과가 나왔습니다.

다익스트라를 반복 사용하다보니 생각없이 heapq을 사용하여 풀었는데,

왜 heapq를 사용하여 작은 값부터 해야 시간초과가 안나는지 이해가 가질 않습니다.

궂이 순서가 필요없어 deque을 사용하여도 될것같은데 아닌가요?

import sys
from collections import deque
input=sys.stdin.readline
INF=int(1e9)

n,m,k=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
       a,b,c=map(int,input().split())
       data[a].append((b,c))

distance=[[INF]*(k) for i in range(n+1)]


def dijkstra(start):
       distance[start][0]=0
       q=deque()
       q.append((0,start))
       while q:
              km,index=q.popleft()
              for i in data[index]:
                     cost=km+i[1]
                     if distance[i[0]][k-1]>cost:
                            distance[i[0]][k-1]=cost
                            distance[i[0]]=sorted(distance[i[0]])
                            q.append((cost,i[0]))
dijkstra(1)
for i in range(1,n+1):
    if distance[i][k-1]==INF:
        print(-1)
    else:
        print(distance[i][k-1])