벨만-포드

[JAVA] 백준 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 해결 방법 벨만-포드 알고리즘을 사용해야 하는 문제이다. 한 정점에서 다른 모든 정점의 최단 경로를 탐색해야 하는데 Cost가 음인 경우 사용 가능하다. 최단 경로를 나타내는 배열을 최댓값으로 초기화 해준 다음 배열을 사용해서 탐색을 진행한다. 정점의 수 - 1 만큼 반복문을 통해 최단 경로를 탐색해주고, 한 번 더 탐색하였을 때 또 최단 경로가 바뀐다고 하면 음의 사이클이 존재한다는 뜻이다. 여기..