1753 - 최단경로

정점의 갯수 V와 간선의 갯수 E가 주어지고, E개만큼의 간선 정보가 입력된다.
정점은 1....V 만큼 있을 때 시작점 V_s 로부터 모든 간선으로의 최단 경로를 출력하는 문제이다.


먼저, 필자는 벨만-포드 알고리즘을 사용했다. 벨만-포드는 O(VE)의 시간복잡도를 가져서 이 문제에서는 적합하기 않다. ( 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000 이기 때문 )

E개의 노드를 차례로 살피면서 각 노드의 최단경로 정보를 갱신한다. 정확도를 위해 (누락되는 경로가 없도록) 각 정점의 갯수 V만큼 갱신을 반복한다. 그래서 O(VE)이다.

당연히 시간초과를 받았지만, 확률상으로 누락되는 경로가 있을까 싶어서 모험을 해봤다.
V번 반복하지 않고 log(V)번 반복해서 시간복잡도 O(E logV)로 도전해봤는데 정답을 맞았다. 운이 좋았다. 그리고 난 쾌재를 불렀다