1753번 - 최단경로
위키 보고 작성한 다익스트라 알고리즘입니다.
STL 의 priority_queue 를 이용해 min_heap 만들었고,
다른 문제가 될만한 부분이 보이질 않네요. 예제 코드도 통과하는데
틀린 케이스를 못 찾겠습니다.
노드 수가 2만개에 에지 weight 도 10을 넘지를 않으니 인트 범위 넘어가서 그런 것도 아닌데..
도와주세요 ㅠㅠ
다익스트라 구현이 잘못되었습니다.
일단 prev_node는 필요없어 보입니다.
그리고 다익스트라는 dist값이 작은 순으로 추출되어야 하는데,
위 코드는 source를 제외한 나머지 모든 정점이 INF로 동일해서
dist의 변경이 반영되지 않습니다.
참고로 위키의 pseudo 코드는 pq를 사용하는 경우에는 적합하지 않습니다.
감사합니다~~^^
댓글을 작성하려면 로그인해야 합니다.
bright2013 7년 전
위키 보고 작성한 다익스트라 알고리즘입니다.
STL 의 priority_queue 를 이용해 min_heap 만들었고,
다른 문제가 될만한 부분이 보이질 않네요. 예제 코드도 통과하는데
틀린 케이스를 못 찾겠습니다.
노드 수가 2만개에 에지 weight 도 10을 넘지를 않으니 인트 범위 넘어가서 그런 것도 아닌데..
도와주세요 ㅠㅠ