dohi   4년 전

채점 번호 : 41314681

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

djm03178   4년 전

다익스트라는 구현 방법에 따라서는 어떤 순서로 정점을 뽑아도 적어도 오답은 안 나오게 될 수도 있습니다. 그런 경우에는 시간이 오래 걸리도록 민들 수 있는지를 봐야 하는데, http://www.secmem.org/blog/201... 에서 실험한 기억으로는 아마도 정점의 수의 제곱에 비례하게 만드는 게 최대였던 것 같습니다. 이 문제에서의 정점의 수는 매우 적기 때문에 해당 코드가 그런 경우라면 아마 저격할 수 없을 것 같습니다.

그리고 설령 틀려야 할 코드가 통과됐다고 해서, 그것을 '데이터가 잘못되었다'고 표현하지는 않습니다. 모든 경우의 수를 다 테스트해볼 수 없기 때문에 테스트 데이터는 언제든지 약할 수 있고, 맞아야 할 코드가 틀리는 것은 잘못되었다고 할 수 있으나 틀려야 할 코드가 맞는 것은 데이터가 약한 것일 뿐 잘못되었다고 할 수는 없습니다.

alex9801   4년 전

다중 간선을 이용하면 O(NM + min(W, M) * M) 정도에 동작하는 데이터를 만들 수 있는데, 가중치 제한도 작아서 시간 내에 도는 것 같네요..

다만 해당 코드가 경로가 없는 경우 처리를 잘못하는 부분이 있어서 따로 데이터 추가 요청을 올렸습니다: https://www.acmicpc.net/board/...

alex9801   4년 전

다른 방법으로 시도했더니 BOJ Stack 기준 2.2초 정도 도는 데이터가 만들어져서 위 글에 같이 첨부하였습니다.

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