음수 사이클1 (c++) 벨만-포드 알고리즘 11657번: 타임머신 https://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 벨만-포드 알고리즘 앞선 다익스트라 알고리즘은 기본적으로 음수의 가중치가 없다는 것을 가정한다. 음수 값으로 나오는 사이클을 만난다면 사이클을 돌 때마다 최솟값을 갱신하기 때문이다. 이번에 볼 알고리즘은 위 경우를 해결하고, 최단 경로도 도출할 수 있다. 벨만-포드 알고리즘은 최단 거리의 특성을 이용하여 알고리즘을 구성한다. 시작점에서 .. 2024. 1. 9. 이전 1 다음