[JAVA] 백준 11657- 타임머신(벨만 포드)

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

11657번: 타임머신

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Bus{
    int start, end, weight;
    public Bus(int start, int end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}
public class Main{
    static int n, m;
    static final int INF = 100000000;
    static ArrayList<Bus> list = new ArrayList<>();
    static long[] dist;

    public static boolean bellmanFord(){
        boolean cycle = false;
        dist[1] = 0;

        for(int i=0; i<=n; i++){
            for(int j=0; j<m; j++){
                int s = list.get(j).start;
                int e = list.get(j).end;
                int w = list.get(j).weight;

                if(dist[s]!=INF && dist[s] + w < dist[e]){ // 목적지까지 최단 경로 > 시작점 최단 경로 + 목적지까지 가중치 일 때
                    dist[e] = dist[s]+w;
                    if(i==n) cycle = true; // n번의 라운드 반복 후에 n번째 라운드에서도 최단경로가 갱신되면 음의 사이클임
                }
            }
        }
        return cycle;
    }
    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());

        dist = new long[n+1];

        Arrays.fill(dist, INF);

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int A= Integer.parseInt(st.nextToken());
            int B= Integer.parseInt(st.nextToken());
            int C= Integer.parseInt(st.nextToken());

            list.add(new Bus(A, B, C));
        }
        StringBuilder sb = new StringBuilder();
        if(bellmanFord()){
            sb.append(-1+"\n");
        }else {
            for(int i=2; i<=n; i++){
                sb.append(dist[i]==INF ? -1 : dist[i]).append("\n");
            }
        }
        System.out.println(sb);
    }
}