[자바] 백준 11657번: 타임머신

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

 

11657번: 타임머신

밸만포드 알고리즘을 이용한다.

 

 

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 다음의 과정을 N-1번 반복한다.

 3-1. 전체 간선 E개를 하나씩 확인한다.

 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

 

만약 음수 간선 순환을 확인하고 싶다면  3번의 과정을 한 번 더 수행한다.

이 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

 

 

다익스트라는

매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

 

벨만포드는

매번 모든 간선을 전부 확인한다

 

벨만포드는 다익스트라 알고리즘에 비해 시간복잡도가 조금 더 크지만

음수 간선이 있는 경우도 계산 가능하다는 장점이 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P11657 {
	static int n, m;
	static long[] distance;
	static int[][] edges;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		edges = new int[m][3];
		distance = new long[n + 1];
		for (int i = 0; i < n + 1; i++) {
			distance[i] = Integer.MAX_VALUE;
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			edges[i][0] = Integer.parseInt(st.nextToken());
			edges[i][1] = Integer.parseInt(st.nextToken());
			edges[i][2] = Integer.parseInt(st.nextToken());

		}

		boolean negative_cycle = bellman_ford(1);

		if (negative_cycle)
			System.out.println(-1);
		else {
			for (int i = 2; i < n + 1; i++) {
				if (distance[i] == Integer.MAX_VALUE) {
					System.out.println(-1);
				} else {
					System.out.println(distance[i]);
				}
			}
		}
	}

	static boolean bellman_ford(int start) {
		distance[start] = 0;

		for (int i = 0; i < n; i++) {

			for (int j = 0; j < m; j++) {
				int cur_node = edges[j][0];
				int next_node = edges[j][1];
				int edge_cost = edges[j][2];

				if (distance[cur_node] != Integer.MAX_VALUE && distance[next_node] > distance[cur_node] + edge_cost) {
					distance[next_node] = distance[cur_node] + edge_cost;

					if (i == n - 1) {
						return true;
					}
				}
			}
		}
		return false;
	}
}

distance를 int형으로 썼을 때는 출력초과가 났는데

long형으로 바꾸니 정답처리 됐다.

음수 크기가 너무 작아져서 언더플로우가 난것같다.(추측)