djm03178   2년 전

이 문제를 푸는 널리 알려진 방법은 "정점마다 최대 K개의 최단경로를 저장하고, (정점, i번째 최단경로)를 하나의 정점으로 두는 다익스트라"입니다.

하지만 이렇게 할 경우 정점이 NK개, 간선이 MK개인 그래프가 되기 때문에 일반적인 다익스트라는 O(MKlog(NK))를 피할 수 없게 됩니다.

중복 간선이 허용되지 않기 때문에 실질적인 M의 최대는 약 백만이지만, 그렇다 하더라도 MK는 최대 약 1억이며, 간선의 가중치 제한 때문에 log(NK) 부분이 최악의 경우 어느 정도까지 작용할지는 모르겠지만 현재의 제한에서 쉽게 시도해볼 수 있는 것이 아님은 명확합니다.

실제로 이러한 데이터가 있었다면 대부분의 코드는 시간 제한 내에 돌지 못했을 것이라고 생각하며, 데이터를 확인해 본 결과로는 M은 최대 30만 이하, MK는 최대 300만이었습니다.

- AC: https://www.acmicpc.net/source...

- RTE: https://www.acmicpc.net/source...

현재 상황에서 최악의 데이터를 넣으면 매우 무시무시한, 심하면 살아남는 코드가 0개에 가까워지는 문제가 될 수도 있다고 생각되기에, 현재 데이터에 tight한 조건으로 문제를 수정해주셨으면 합니다.

startlink   2년 전

수정했습니다.

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