[BaekJoon] 11657 타임머신 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있습니다.
• 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간을 의미합니다.
• 시간 C가 양수가 아닌 경우도 있는데, C = 0인 경우는 순간 이동을 하는 경우이고 C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우입니다.
• 1번 도시에서 출발하여 나머지 도시로 가는 가장 빠른 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 500보다 작거나 같은 도시의 개수 N, 1보다 크거나 같고 6,000보다 작거나 같은 버스 노선의 개수 M이 주어지고 두 번째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C가 주어집니다.
  • 1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000
• 출력: 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫 번째 줄에 -1을 출력하고, 그렇지 않다면 N - 1개 줄에 걸쳐 각 줄에 1번 도시에서 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력합니다. 만약 해당 도시로 가는 경로가 없다면 -1을 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
	static final long INF = 30000000001L;
	static int N, M;
	static Edge[] edges;
	static long[] weight;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		edges = new Edge[M];
		for(int edge = 0; edge < M; edge++) {
			int A = scanner.nextInt(), B = scanner.nextInt(), C = scanner.nextInt();
			edges[edge] = new Edge(A, B, C);
		}
	}
	
	static void solution() {
		if(Bellman_Ford(1)) {
			System.out.println(-1);
			return;
		}
		for(int v = 2; v <= N; v++)
			sb.append(weight[v] == INF ? -1 : weight[v]).append('\n');
		System.out.println(sb);
	}
	
	static boolean Bellman_Ford(int start) {
		weight = new long[N + 1];
		Arrays.fill(weight, INF);
		weight[start] = 0L;
		boolean isChanged = false;
		
		outerloop:
		for(int v = 1; v <= N; v++) {
			isChanged = false;
			for(Edge e : edges) {
				if(weight[e.start] == INF) continue;
				if(weight[e.end] > weight[e.start] + e.weight) {
					weight[e.end] = weight[e.start] + e.weight;
					isChanged = true;
					// 음수 사이클 존재 여부 확인
					if(v == N) {
						isChanged = true;
						break outerloop;
					}
				}
			}
			if(!isChanged) break;
		}
		return isChanged;
	}
    
    public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Edge {
		int start, end, weight;
		public Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
	}
    
    static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			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());
		}
	}
}