minusie357   4년 전

안녕하세요. 이 문제를 다익스트라를 여러 번 호출해서 해결하는 것이 아니라, 출발지가 변경되지 않으므로 단 한 번의 다익스트라로 모든 계산을 끝내려고 했습니다.

다익스트라 알고리즘 수행 도중에 G-H 구간을 지나가면, 그 구간부터 더 깊은 깊이를 들어가는 모든 최단경로를 true로 설정하여 최단 경로 비용과 G-H 구간을 지났는지 여부를 함께 반환합니다.

이렇게 하면, 결과를 출력할 때 최단 경로들 중에서 G-H 구간을 지나면서 목적지 후보로 등록된 요소들만 출력하기 위한 배열에 push해서 출력하도록 하였는데, 50% 부분에서 틀렸다고 뜹니다. 제 알고리즘에 어떠한 반례나 허점이 있는지 궁금합니다 ㅠㅠ.

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