ris33   6달 전

17부터 ~ 23줄까지

heap을 이용하여 문제를 풀었습니다.

마이너스를 붙여 최소힙을 최대힙으로 이용한 케이스인데,

마이너스를 붙이지 않고 최소힙으로 이용할 시 시간초과가 생깁니다.

단지 음수를 붙이고 최소 최대힙을 바꾼것 뿐인데 결과가 달라지는 이유가 궁금합니다.


아래는 음수를 안붙이고 최소힙으로 푼 코드입니다.

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])


댓글을 작성하려면 로그인해야 합니다.