import sys
import heapq
input=sys.stdin.readline
n,m,k=map(int,input().split())
data=[[] for i in range(n+1)]
distance=[[] for i in range(n+1)]
for i in range(m):
a,b,c=map(int,input().split())
data[a].append((b,c))
q=[]
heapq.heappush(q,(0,1))
distance[1].append(0)
while q:
km,index=heapq.heappush(q)
for i in data[index]:
cost=km+i[1]
if len(distance[i[0]])<k:
heapq.heappush(distance[i[0]],cost)
heapq.heappush(q,(cost,i[0]))
elif distance[i[0]][k-1]>cost:
heapq.heappop(distance[i[0]])
heapq.heappush(distance[i[0]], cost)
heapq.heappush(q,(cost,i[0]))
print(distance)
for i in range(1,n+1):
if len(distance[i])<k:
print(-1)
else:
print(distance[i][k-1])
ris33 2년 전
17부터 ~ 23줄까지
heap을 이용하여 문제를 풀었습니다.
마이너스를 붙여 최소힙을 최대힙으로 이용한 케이스인데,
마이너스를 붙이지 않고 최소힙으로 이용할 시 시간초과가 생깁니다.
단지 음수를 붙이고 최소 최대힙을 바꾼것 뿐인데 결과가 달라지는 이유가 궁금합니다.
아래는 음수를 안붙이고 최소힙으로 푼 코드입니다.