다익스트라는 구현 방법에 따라서는 어떤 순서로 정점을 뽑아도 적어도 오답은 안 나오게 될 수도 있습니다. 그런 경우에는 시간이 오래 걸리도록 민들 수 있는지를 봐야 하는데, http://www.secmem.org/blog/201... 에서 실험한 기억으로는 아마도 정점의 수의 제곱에 비례하게 만드는 게 최대였던 것 같습니다. 이 문제에서의 정점의 수는 매우 적기 때문에 해당 코드가 그런 경우라면 아마 저격할 수 없을 것 같습니다.
그리고 설령 틀려야 할 코드가 통과됐다고 해서, 그것을 '데이터가 잘못되었다'고 표현하지는 않습니다. 모든 경우의 수를 다 테스트해볼 수 없기 때문에 테스트 데이터는 언제든지 약할 수 있고, 맞아야 할 코드가 틀리는 것은 잘못되었다고 할 수 있으나 틀려야 할 코드가 맞는 것은 데이터가 약한 것일 뿐 잘못되었다고 할 수는 없습니다.

dohi 4년 전
채점 번호 : 41314681
우선순위 큐에 삽입하는 과정에서 정점의 거리 대신에 간선의 가중치를 삽입하였는데 AC 받았습니다. 이렇게 구현해도 상관없는 것인지 아니면 데이터가 잘못된 것인지 궁금합니다.