벨만포드

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 풀이과정 이 문제는 벨만 포드의 대표적인 기본 문제이다. 그 이유는 타임머신으로 시간을 되돌아가는 경우가 있으므로 가중치가 음수가 될 수 있기 때문이다. 가중치에 음수가 있다면 다익스트라가 아닌, 벨만 포드 알고리즘을 생각해야 한다. 문제에 있는 '시간을 무한히 오래전으로 되돌릴 수 있다면'이라는 말은 '음의 사이클이 존재한다면' 뜻이다..

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 풀이과정 이 문제는 벨만포드의 대표적인 기본 문제이다. 그 이유는 타임머신으로 시간을 되돌아가는 경우가 있으므로 가중치가 음수가 될 수 있기 때문이다. 가중치에 음수가 있다면 다익스트라가 아닌, 벨만포드 알고리즘을 생각해야한다. 문제에 있는 '시간을 무한히 오래전으로 되돌릴 수 있다면'이라는 말은 '음수 사이클이 존재한다면'이라는 뜻이다..