BOJ 11657 - 타임머신

11657번: 타임머신

 

N(1≤N≤500) 개의 도시, 버스가 M(1≤M≤6,000) 개

각 버스는 A, B, C로 나타낼 수 있는데 A는 시작도시, B는 도착도시, C는 버스를 타고 걸리는 데 걸리는 시간

-10,000 ≤ C ≤ 10,000

1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간은?

음수가 존재하는 최단거리이다. 출발 도착이 존재하기 때문에 방향 그래프이다.

1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 -1을 출력

⇒ 1번에서 출발해서 순환이 존재 + 비용의 합이 음수 = 무한히 오래 전으로 돌릴 수 있다.

도달할 수 없다 = 경로가 없다.

벨만-포드를 통해 음수 가중치를 처리 + 음수 사이클 감지

package boj;

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

public class BOJ11657 {
	static class Edge {
		int from;
		int to;
		int cost;

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

	static FastReader scan = new FastReader();
	static int N, M;
	static Edge[] edges;

	static void input() {
		N = scan.nextInt();
		M = scan.nextInt();
		edges = new Edge[M];

		for (int i = 0; i < M; i++) {
			edges[i] = new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt());
		}
	}

	static void solve() {
		long[] dist = new long[N + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 0;

		boolean hasNegativeCycle = false;

		for (int i = 1; i <= N; i++) {
			for (Edge edge : edges) {
				if (dist[edge.from] != Integer.MAX_VALUE &&
					dist[edge.to] > dist[edge.from] + edge.cost) {
					dist[edge.to] = dist[edge.from] + edge.cost;

					if (i == N) {
						// N인데도 갱신? -> 음수 사이클 존재
						hasNegativeCycle = true;
						break;
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		if (hasNegativeCycle) {
			System.out.println(-1);
		} else {
			for (int i = 2; i <= N; i++) {
				if (dist[i] == Integer.MAX_VALUE) {
					sb.append(-1).append('\\n');
				} else {
					sb.append(dist[i]).append('\\n');
				}
			}
			System.out.println(sb);
		}
	}

	public static void main(String[] args) {
		input();
		solve();
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}