우선순위 큐를 사용하는 다익스트라를 구현할 때는, 반드시 해당 정점에 대한 거리를 기준으로 우선순위큐에서 뽑아내야합니다. 따라서 dist[next] 을 넣는 식으로 하셔서 푸셔야합니다.
따라서, 제 견해로는, 이제까지 푸신 다익스트라 문제들 모두 다 옳지 않은 구현법이였지만 통과된 경우는 시간 초과가 나는 테스트케이스가 없었던 운이 좋았던 경우라고 생각됩니다. 또는, 그 시간초과가 날만큼 정점이나 간선이 많지 않아 탐색상태가 적은 경우인 것 같아요.
만약, 시간초과가 나는 테스트의 예제가 궁금하시다면 이 문제 게시판의 djm03178님의 데이터 추가요청 게시글을 보시면 djm03178님이 작성한 테스트케이스를 살펴보실 수 있습니다.
san9407 5년 전
재채점 결과 쫘르륵 시간초과나서 질문검색에 있는 간선에서 정점으로 푸는법으로 풀었는데요
전 항상 46번째 줄에 pq.push(make_pair(nextCost,next)) 이런식으로 넣었는데
이 문제는 pq.push(make_pair(dist[next],next))로 풀어야 풀리더라고요
다른 다익스트라 문제도 다 dist[next]로 푸는게 맞나요??
정점으로 푸는것과 간선으로 푸는것 차이가 뭔지 알려주시면 감사하겠습니다.