벨만-포드 알고리즘(가중치가 음수일 때의 최단경로)

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

1865번: 웜홀

 

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

// 벨만-포드에 대해서는 https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm
//https://dragon-h.tistory.com/25, 위 2 사이트를 참조해라

public class  Main {

    static class Bus{

        int start,end,weight;
        public Bus(int start,int end,int weight){
            this.start = start;
            this.end = end;
            this.weight =weight;
        }
    }


    private static int n,m;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static long distance[];

    private static Bus buses[];

    private static final int INF = 500*10000+1;

    public static void main(String[] args) throws IOException {

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

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

    buses = new Bus[m+1];

    for(int x = 0;x < m;x++){

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        int weight = Integer.parseInt(st.nextToken());

        // 단방향
        buses[x] = new Bus(start,end,weight);

    }

        StringBuilder sb = new StringBuilder();

        boolean bell_result = bell();
        if(bell_result == false)
            sb.append(-1).append("\n");
        else
        {
            for(int x = 2; x <= n; x++) {

             if(distance[x] != INF)
                sb.append(distance[x]).append("\n");
             else
                sb.append(-1).append("\n");
            }
        }
       System.out.println(sb);

    }

    static boolean bell(){

        //시작 노드는 [1]
        distance[1] = 0;

        // (n-1)번 반복
        for(int x = 1; x <= n;x++){

            for(int y = 0; y < m; y++)
            {
                Bus temp = buses[y];

                if(distance[temp.start]!=INF && distance[temp.end] >distance[temp.start] + temp.weight ) {

                    distance[temp.end] = distance[temp.start] + temp.weight;
                    // n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재(https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm)
                    if(x == n)
                        return false;
                }
            }

        }

        return true;
    }

}