boj 11657: 타임머신

• 벨만 포드 알고리즘: 정점 개수가 V개일 때, 최단 경로는 최대 V-1 개의 간선으로 이루어져 있다.
  • 가중치가 음수인 경우도 사용 가능하다
  • 시작점이 1개이다
  • 음수 사이클을 검사할 수 있다
  • 시간복잡도 O(VE)
  • E <= V^2 이므로 시간복잡도는 O(V^3)
  • 벨만 포드 알고리즘에선 인접 행렬/인접 리스트가 필요 없다. - 인접 행렬/인접 리스트는 어떤 정점과 연결되어 있는 간선을 효율적으로 탐색하는 것인데, 벨만 포드 알고리즘은 모든 정점/간선을 모두 검사한다. 따라서 효율적인 자료구조가 필요 없음 

c.f. 다익스트라 알고리즘: 가중치가 음수인 경우는 사용할 수 없다.

 

이 문제에서 음수 사이클이 존재하는 경우 해당 도시로 가는 시간을 무한히 되돌릴 수 있다.

최단 경로는 최대 V-1개의 간선으로 이루어져있다고 했으니까 V-1단계까지 벨만 포드 알고리즘을 적용하면 최단 경로가 나올 것이다.

이 때, 음수 사이클을 찾는 방법은 한 단계를 더 했을 때(i=n), 최단 경로가 변경된다. = 최단 경로가 존재하지 않는다.

즉 아래 코드에서 최단 경로가 변경됐는데 i=n일 때 음수사이클 존재를 확인한다.

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		List<Bus> buses = new ArrayList<Bus>();
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();
			buses.add(new Bus(start, end, time));
		}
		long dist[] = new long[n + 1];
		Arrays.fill(dist, Long.MAX_VALUE);
		dist[1] = 0;
		boolean isNegativeCycle = false;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < m; j++) {
				int start = buses.get(j).start;
				int end = buses.get(j).end;
				int time = buses.get(j).time;
				if (dist[start] != Long.MAX_VALUE && dist[end] > dist[start] + time) {
					dist[end] = dist[start] + time;
					if (i == n) {
						isNegativeCycle = true;
					}
				}
			}
		}
		if (isNegativeCycle) {
			System.out.println("-1");
		} else {
			for (int i = 2; i <= n; i++) {
				if (dist[i] == Long.MAX_VALUE) {
					System.out.println("-1");
				} else {
					System.out.println(dist[i]);
				}
			}
		}
	}
}
class Bus {
	int start, end, time;
	public Bus(int start, int end, int time) {
		this.start = start;
		this.end = end;
		this.time = time;
	}
}