[boj] 11657 - 타임머신(shortest path, bellman-ford)
www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 최단거리 문제이다. 간선의 가중치가 음수인 케이스가 있으므로 다익스트라 알고리즘으로 풀 수 없고, 벨만포드 알고리즘으로 풀어야 한다. 노드가 n개일 때, 최대 n-1개의 간선에 대하여 최단거리를 계산해준다. 따라서 시간복잡도는 n개의 노드에 대해서 n-1개의 간선을 검사하므로 O(V*E) = O(V^3)이 나온다. 다만 음수사이클이 있는 경우를 계산하..
2021. 3. 29.
