백준 - 타임머신(11657) - 벨만포드 - Java

1. 문제

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

2. 풀이

참고 풀이 - C++
참고 풀이 - Java

다익스트라로 풀려고 했지만 무리였다..

🥲음수 가중치 + 음수 사이클 판단 = 벨만 포드를 쓰도록 하자.

✨핵심 Point

1. 시작도드의 distance 배열은 반드시 0으로 시작해야한다!

d[1] = 0;

2. '만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. ' 이라는 조건이 음수 사이클일 경우 -1을 출력하라는 뜻이다. + distance배열이 무한대일경우에도 마찬가지로 -1을 출력하라는 뜻이였다.

// 마지막 사이클 판단.
for(int i = 0; i < M; i++){
	Node node = list.get(i);
	if(d[node.a] != Long.MAX_VALUE && d[node.b] > d[node.a] + node.cost){
		System.out.println(-1);
		return;
	}
}

3. 전체 코드

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

public class Main {
    public static void main(String args[]) throws IOException{
        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());
        
        long d[] = new long[N+1];
        ArrayList<Node> list = new ArrayList<>();
        
        for(int i = 0; i <= N; i++){
            d[i] = Long.MAX_VALUE;
        }
        d[1] = 0;
        
        for(int m = 0; m < M; m++){
            st = new StringTokenizer(br.readLine(), " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            long C = Long.parseLong(st.nextToken());
            
            list.add(new Node(A, B, C));
        }
        
        for(int i = 0; i < N - 1; i++){
            for(int j = 0; j < M; j++){
                Node node = list.get(j);
                
                if(d[node.a] != Long.MAX_VALUE && d[node.b] > d[node.a] + node.cost){
                    d[node.b] = d[node.a] + node.cost;
                }
            }
        }
        
        for(int i = 0; i < M; i++){
            Node node = list.get(i);
            if(d[node.a] != Long.MAX_VALUE && d[node.b] > d[node.a] + node.cost){
                System.out.println(-1);
                return;
            }
        }
        
        for(int i = 2; i <= N; i++){
            if(d[i] == Long.MAX_VALUE){
                System.out.println(-1);
            } else{
                System.out.println(d[i]);
            }
        }
    }
    
    public static class Node {
        int a;
        int b;
        long cost;
        
        public Node(int a, int b, long cost){
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }
}