벨만 - 포드

Bellman - Ford 알고리즘은 다익스트라 알고리즘과 달리 모든 노드를 주기적으로 갱신시켜주기 때문에 \(O(V*E)\)가 걸리지만 음의 가중치를 포함한 노드들에 대해서도 성공적으로 탐색할 수 있다. 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 대표적인 벨만 - 포드를 사용한 문제이다. 우선 각 간선의 수만큼 입력을 받는데 편하게 계산하기 위해 좌표들에 -1씩 해서 받아줬다. cin >> ..