BOJ. 11657번. 타임머신

 

    이번 문제는 벨만-포드 알고리즘을 활용한 문제다. 실제 코드 상에서도, 각 정점을 돌아보면서 최소비용을 갱신해 나가는 형태가 다익스트라(우선순위 큐)를 사용하지 않은 코드랑 비슷했다. 물론 음의 가중치가 포함된 문제라 다익스트라로는 해결할 수 없다. + 추가로 거리를 계산할 때 오버플로우가 나는 바람에 출력초과가 나왔다. 넘칠 것 같으면 처음부터 long으로 넉넉하게 잡아주는 것도 실수를 줄이는 방법이 될 것 같다.

www.acmicpc.net/problem/11657

11657번: 타임머신

 

package week_12;

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

public class Day5BOJ11657 {

	static int n, m;
	static long[] minDist;
	static final int INF = 10000 * 10000 + 1;
	static ArrayList<Edge> list = new ArrayList<Edge>();

	static class Edge {
		int from, to, cost;

		public Edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		minDist = new long[n + 1];
		Arrays.fill(minDist, INF);

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			list.add(new Edge(from, to, cost));
		}

//		System.out.println(Arrays.toString(minDist));
		if (BellmanFord()) {
			for (int i = 2; i <= n; i++) {
				System.out.println((minDist[i] == INF) ? -1 : minDist[i]);
			}
		} else {
			System.out.println(-1);
		}
	}

	private static boolean BellmanFord() {
		minDist[1] = 0;

		// 각 정점 돌면서 거리 갱신
		for (int i = 2; i <= n; i++) { // 남은 각 정점에서
			for (int j = 0; j < m; j++) { // 간선개수만큼
				Edge cur = list.get(j);
				int from = cur.from;
				int to = cur.to;
				int cost = cur.cost;
				// 더 작은 값 있으면 갱신
				if (minDist[from] != INF && minDist[to] > minDist[from] + cost) {
					minDist[to] = minDist[from] + cost;
				}
			}
		}

		// 다 돌리고 나서 음수 사이클 확인
		for (int i = 0; i < m; i++) { 
			Edge cur = list.get(i);
			int from = cur.from;
			int to = cur.to;
			int cost = cur.cost;
			if (minDist[from] != INF && minDist[to] > minDist[from] + cost) {
				return false;
			}
		}
//		System.out.println(true);
		return true;
	}
}