다익스트라 방식에서 아래 테스트 케이스를 통과못하지만, 제출했을때 통과되었습니다. (채점 번호 : 59262341)

한 교차로에 동일 수치심(해당 교차로까지 최대 비용이 동일한 경우)으로 도달할 경우 무조건 후자를 버리는 로직으로 짜도 통과가 되었습니다.

무조건 버리는 것이 아니라, 최대 비용이 더 적을 경우 한 번 더 갱신을 해줘야 합니다. 하지 않을 경우에 C 보다 작은 경로를 찾지 못할 수 있습니다.

59262341 코드로는 위 케이스에서 -1이 나오지만, 실제 정답은 5입니다.(1 -> 4 -> 5 -> 3-> 6)

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