백준 11657 - 타임머신 (java)

https://www.acmicpc.net/problem/11657

음수 가중치가 존재하고, 음의 사이클이 존재할 때 사용하는 벨만포드 알고리즘을 이용하는 문제이다.

시작점을 제외한 dist 배열에 INF를 넣고 != INF를 통해 시작점과 연결 되어있는지를 확인한다.

버스노선을 N-1번 순회하여 최단거리를 파악하고 한번 더 최단거리를 갱신했을 때 변화가 있다면 무한정으로 음수로 갈 수 있는 상태이다.

N-1번 순회하는 이유는 음수가 포함되어있기 때문에 1-2를 2의 시간에 갈 수 있다고 가정하면 1-2-3-1-2 이었을 때 1의 시간이 걸릴 수 있다. 따라서 N-1 번 반복하여 가능한 최단거리로 갱신을 하는 것이다.

public class Main {  
  
	static int N;  
	static int M;  
  
	static Bus[] bus_way;  
	static long[] dist; //무한정 음수로 갈 수 있기 때문에 long으로 해야한다.
	static final int INF = 987654321;  
	static class Bus{  
		public int start;  
		public int end;  
		public int time;  
  
		public Bus(int start, int end, int time){  
			this.start = start;  
			this.end = end;  
			this.time = time;  
		}  
	}  
  
	public static void main(String[] args) throws Exception {  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		StringTokenizer st;  
		StringBuilder sb = new StringBuilder();  
  
		st = new StringTokenizer(br.readLine());  
  
		N = Integer.parseInt(st.nextToken());  
		M = Integer.parseInt(st.nextToken());  
  
		bus_way = new Bus[M];  
  
		for(int i = 0; i < M; i++){  
			st = new StringTokenizer(br.readLine());  
  
			int start = Integer.parseInt(st.nextToken());  
			int end = Integer.parseInt(st.nextToken());  
			int time = Integer.parseInt(st.nextToken());  
  
			bus_way[i] = new Bus(start, end, time);  
		}  
  
		dist = new long[N+1];  
		Arrays.fill(dist, INF);  
  
		if(bell()){  
			for(int i = 2; i < dist.length; i++){  
				if(dist[i] == INF){  
					sb.append(-1).append("\n");  
				}  
				else{  
					sb.append(dist[i]).append("\n");  
				}  
		}  
		}else{  
			sb.append(-1);  
		}  
  
		System.out.print(sb);  
	}  
  
	public static boolean bell(){  
		dist[1] = 0;  
  
		for(int k = 0; k < N-1; k++){  
			for(int i = 0; i < bus_way.length; i++){  
				Bus bus = bus_way[i];  
  
				if(dist[bus.start] != INF && dist[bus.end] > dist[bus.start] + bus.time){  
					dist[bus.end] = dist[bus.start] + bus.time;  
				}  
			}  
		}  
  
		for(int i = 0; i < bus_way.length; i++){  
			Bus bus = bus_way[i];  
  
			if(dist[bus.start] != INF && dist[bus.end] > dist[bus.start] + bus.time){  
				return false;  
			}  
		}  
		return true;  
	}  
}