hayman42   4년 전

https://www.acmicpc.net/source/13768650 가 틀린 코드인데 맞습니다.

보시면 메모리를 좀 많이 잡아먹는데 사실 이 부분은 중요하지 않은게 node 구조체가 쓸데 없이 큰걸 그냥 고치지 않아서 그런거고,

그 보다 의문점인 것은 시간입니다.

위 코드는 각 정점을 최대 k 번 방문하게 만든 다익스트라 알고리즘인데요, 일단 대략적으로 아래의 케이스같은 경우 시간초과가 납니다.

그리고 시간초과가 날 수 밖에 없다고 생각하는 이유는 정점을 k 번 방문하면 같은 간선도 k 번 방문한다는 이야기인데,

문제 조건에 의하면 100만 ( 200만이지만 질문 글 보니 중복 간선이 없다고 하네요. 이 부분 아래 글대로 조건 추가 요청합니다. 푸는데 영향을 줄 수 있을 것 같습니다. ) 개의 간선 또한 최대 k 번 중복 방문 가능하다는 이야기이니 사실상 간선이 100만 * 100 = 1억개 있는 거나 마찬가지라 그런거로 생각합니다.

실제 1등님의 코드를 ideone 에서 돌려봐도 아래 케이스에 대해 0.5 초가 나오기도 합니다.

그리고 궁금한 점도 있는게 1등 코드 참조 결과 저처럼 정점을 k 번 이상 방문 되었을 시 continue 하는 것이 아니라
거리 pq 를 둬서 방문한 시점에서의 거리가 저장되어있는 거리의 최댓값이 더 크면 continue 하는 것이 정해로 보여지는데요,

이렇게 해도 결국 k 번 방문하게 될 것이므로 제 코드와 시간 복잡도가 비슷한 것 아닌가요? 여러 케이스를 돌려 본 결과 매우 빠르게 돌아가서 어떤 차이점이 있는지도 궁금합니다.

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