wjddms206   1년 전

다익스트라를 사용해서 문제를 풀었습니다. (우선순위 큐 사용)
계속 시간초과만 났었습니다. 
그러나 질문을 토대로 어찌어찌 AC받았지만 얻어걸린 느낌이 많아서 질문드립니다 !!
 
9번째 줄과 19번째 줄에 하이픈(-)을 안붙이면 시간초과가 나더라고요.
그 하이픈 때문에 시간초과가 났던거였어요. 
하이픈을 붙이니까 통과되더라고요.
왜 그런지 알려주실 분 계시나요??? 
부족한 저에게 지식을 나눠주세요ㅠ-ㅠ

onjo0127   1년 전

STL에서 제공하는 우선순위 큐는 Max Heap이어서 가장 큰 원소부터 큐에서 빠져나오게 됩니다.

그런데 다익스트라에서는 코스트가 가장 작은 원소를 꺼내는 게 유리하기 때문에 Min Heap을 이용해야 합니다.

그래서 Max Heap을 그대로 이용해서 원소에 -1을 곱해 Min Heap으로 바꾼 겁니다. -1을 곱하면 순서가 뒤집혀서 반대로 빠져나오니까요 ㅎㅎ

wjddms206   1년 전

onjo0127님 

크 넘넘 대단하십니다. 감사합니다

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