[백준] 11657 타임머신 [JAVA]

문제링크 : www.acmicpc.net/problem/11657

11657번: 타임머신

최단거리 알고리즘은 보통 다익스트라나 플로이드워셜만 풀어왔다.

이 문제는 벨만포드 알고리즘으로 풀린다.

벨만포드 알고리즘은 음수 가중치가 있는 경우의 문제의 경우를 풀 수 있는 것으로 사이클의 존재 또한 알 수 있다.

import java.io.*;
import java.util.*;

public class Main {
	
	public static class Node{
		int start;
		int dest;
		long cost;
		public Node() {}
		public Node(int c,int a,long b) {
			start = c;
			dest = a;
			cost = b;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		ArrayList<Node> adj = new ArrayList<Node>();
		long dist[] = new long[N+1];
		for(int i=1;i<=N;i++) {
			dist[i] = 987654321;
			
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			long c = Integer.parseInt(st.nextToken());
			adj.add(new Node(s,e,c));
		}
		boolean isCycle = false;
		dist[1] = 0;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<M;j++) {
				int s = adj.get(j).start;
				int e = adj.get(j).dest;
				long c = adj.get(j).cost;
				if(dist[e] > dist[s] + c && dist[s]!= 987654321) {
					if(i==N) {
						isCycle=  true;
					}
					dist[e] = dist[s]+ c;
				}
			}
		}
		if(isCycle) {
			System.out.println(-1);
		}else {
			for(int i=2;i<=N;i++) {
				if(dist[i]==987654321) {
					System.out.println(-1);
				}else {
					System.out.println(dist[i]);
				}
			}
		}
	}

}