백준 JAVA 11657번 타임머신

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

11657번: 타임머신

 

음의 가중치가 있으므로 다익스트라 알고리즘으로는 해결할 수 없다. 따라서 벨만포드 알고리즘을 이용한다.

 

벨마포드 알고리즘을 이용함에 있어서 음의 사이클이 있으면 안되므로 해당 로직을 한 번더 실행하여 음의 사이클이 있는지 체크해준다.

 

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


class node{
    int start;
    int end;
    int cost;

    public node(int start,int end, int cost) {
        this.end = end;
        this.start=start;
        this.cost = cost;
    }

}


public class Main {

    static int v;
    static int e;
    static List<node>list;
    static long[] distance;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        v = Integer.parseInt(s[0]);
        e = Integer.parseInt(s[1]);
        list = new ArrayList<>();
        distance = new long[v + 1];
        for (int i = 1; i <= v; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        int a, b, c;


        for (int i = 0; i < e; i++) {
            String[] s1 = br.readLine().split(" ");
            a = Integer.parseInt(s1[0]);
            b = Integer.parseInt(s1[1]);
            c = Integer.parseInt(s1[2]);
            list.add(new node(a,b, c));
        }


        StringBuilder sb = new StringBuilder();

        if(bell()){
            for (int i = 2; i <= v; i++) {
                if (distance[i] == Integer.MAX_VALUE) {
                    sb.append(-1).append("\n");
                    continue;
                }
                sb.append(distance[i]).append("\n");
            }
        }
        else{
            sb.append(-1);
        }

        System.out.println(sb.toString());
    }


    public static boolean bell() {
        distance[1] = 0;
        for(int i=1; i<=v; i++){
            for(node a: list){
                if(distance[a.start]==Integer.MAX_VALUE){
                    continue;
                }
                if(distance[a.end]>distance[a.start]+a.cost){
                    distance[a.end]=distance[a.start]+a.cost;
                }
            }
        }

        for(int i=1; i<=v; i++){
            for(node a: list){
                if(distance[a.start]==Integer.MAX_VALUE){
                    continue;
                }
                if(distance[a.end]>distance[a.start]+a.cost){
                    return false;
                }
            }
        }
        return true;
    }
}