[질문] k번째 최단경로 문제 시간복잡도 질문

[익명(49.169)]

https://www.acmicpc.net/problem/1854

이문제 널리 알려진 풀이 시간복잡도 계산하면 O((mk)log(mk)) 같은데 맞음? 입력이 m=2000000 k=100인데 어떻게 시간내에 도는거지

[익명(117.111)]

간선 수는 늘어나지 않기 때문에 정점수만 nk로 늘어나서 m log nk가 맞는듯