han7641   1년 전

다익스트라 여러번 짜본 적이 있어서 자신 있게 제출했는데 30퍼에서 틀려서 당황스럽네요..

어디가 문제일까요? 주석 다 달아놨습니다. 도와주세요 ㅠㅠ

kwakws0627   1년 전

안녕하세요, 일단 반례 먼저 드릴게요

위 코드는 시작 도시부터 다음 도시까지의 거리가 짧은 순이 아닌,

"현재 도시"에서 "다음 도시"까지의 거리(즉, 버스 하나 노선의 길이)가 짧은 순으로 우선순위 큐에서 나옵니다.

(43, 56번째 줄에서 큐에 어떻게 넣는지 확인해주세요)

아래 반례 넣어보시면 아마 1 -> 2, 2 -> 3, 3 -> 4 ,, 이 노선들이 먼저 나올겁니다.

그리고 1 -> 7, 7 -> 6 이 노선들이 가장 나중에 나오고여.


han7641   1년 전

선생님 진짜 감사합니다 ㅠㅠㅠㅠ

반례 주신거 직접 그려보니까 바로 이해됐습니다

거리가 확정된 노드 집합을 한 덩어리라고 생각하고 풀었더니 문제가 생겼던 것 같네요

56줄에 큐에 넣을 때 비용을 시작점 기준으로 바꿔서 넣으니 바로 통과했습니다. 감사합니다 ㅠㅠ

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