백준 1956. 운동

tose33 2022. 8. 29. 13:57

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의

www.acmicpc.net

시작 노드에서 다른 노드를 거쳐 다시 시작 노드로 돌아오는 최소 비용을 구하는 문제였다.

플로이드 와샬 알고리즘으로 모든 노드들의 각 최소 거리를 구해서, 시작 노드 a에서 b노드 까지의 최소 거리 + b에서 a노드 까지의 최소 거리중 가장 작은 값을 구하면 된다.

그런데 나는 보통 그냥 다익스트라를 모든 노드에 대하여 돌려서 쓴다.

왜냐하면 대부분의 경우 다익스트라가 훨씬 빠르기 때문이다.

이 문제에서 다익스트라의 시간복잡도는 O(E * logV) = 400^2 * 20

플로이드 와샬의 시간복잡도는 O(V^3) = 400^3 이다.