[백준] 11657**/ 타임머신 (골드4)

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

벨만-포드 알고리즘

• 다익스트라와 다르게 음수도 간선에 존재할 수 있음
• 시간복잡도 O(V*E)
  진행과정

1. 최단 거리 테이블을 무한대로 초기화
2. 출발 노드를 설정
3. 다음의 과정을 (V(=정점) - 1)번 반복한다.

• 모든 간선 E개를 하나씩 확인
• 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
• 만약 음수 간선 순환이 발생하는지 체크하고 싶다면, 3번 과정을 한 번만 더 수행
  --> 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ArrayList<Edge>[] bus = new ArrayList[n+1];
        int[] ans = new int[n+1];
        Arrays.fill(ans, Integer.MAX_VALUE); // 1. 최단 거리 테이블 무한대(=길을 모른다)로 초기화
        for(int i=0;i<=n;i++){
            bus[i] = new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            bus[from].add(new Edge(to,val));
        }

        // 거리 최소값 구하기 - 벨만-포드 알고리즘
        // 2. 출발 노드 설정
        ans[1] = 0;
        // 3. v-1번 반복
        for(int i=1; i<n;i++){
            // 모든 간선 확인
            for(int j=1;j<=n;j++){
                for(Edge e : bus[j]){
                    int to = e.to;
                    int val = e.val;
                    if(ans[j] != Integer.MAX_VALUE && ans[to]>ans[j]+val){
                        ans[to] = ans[j]+val;
                    }
                }
            }
        }

        // 음수 간선 순환이 있는지 확인
        boolean loop = false;

        for(int j=1;j<=n;j++){
            for(Edge e : bus[j]){
                int to = e.to;
                int val = e.val;
                if(ans[j] != Integer.MAX_VALUE && ans[to]>ans[j]+val){
                    loop = true;
                    break;
                }
            }
            if (loop) break;
        }


        // 무한히 오래 전으로 되돌릴 수 있다면 -1 출력
        if(loop){
            System.out.println(-1);
            return;
        }
        // 아니면 값 출력
        for(int i=2;i<=n;i++){
            if(ans[i] == Integer.MAX_VALUE) System.out.println(-1);
            else System.out.println(ans[i]);
        }
    }
    static class Edge{
        int to; int val;
        Edge(int to, int val){
            this.to = to; this.val=val;
        }
    }
}

=> 출력 초과로 StringBuilder사용

StringBuilder sb = new StringBuilder();
for(int i=2; i<=n; i++) {
    if(ans[i] == Integer.MAX_VALUE) {
        sb.append(-1).append('\n');
    } else {
        sb.append(ans[i]).append('\n');
    }
}
System.out.print(sb);

=> 출력 문제가 아니었음
int가 아니라 long으로 사용해야 함

long[] ans = new long[n+1];

===
10/15

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ArrayList<Edge>[] bus = new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            bus[i] = new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            bus[from].add(new Edge(to,val));
        }
        long[] dis = new long[n+1];
        Arrays.fill(dis, Long.MAX_VALUE);
        dis[1]=0;
        for(int i=1;i<n;i++){
            for(int j=1;j<=n;j++){
                for(Edge b : bus[j]){
                    int to = b.to;
                    int val = b.val;
                    if(dis[j]!=Long.MAX_VALUE && dis[to]>dis[j]+val){
                        dis[to] = dis[j]+val;
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            for(Edge b : bus[i]){
                int to = b.to;
                int val = b.val;
                if(dis[i]!=Long.MAX_VALUE && dis[to]>dis[i]+val){
                    System.out.println(-1);
                    return;
                }
            }
        }

        for(int i=2;i<=n;i++){
            if(dis[i]==Long.MAX_VALUE) System.out.println(-1);
            else System.out.println(dis[i]);
        }

    }

    static class Edge{
        int to; int val;
        Edge(int to, int val){
            this.to=to; this.val=val;
        }
    }

}

v까지가 아니라 v-1까지
dis[j]>dis[to]+val가 아니라 dis[to]>dis[j]+val
마지막에 출력할때도 max_value인지 확인

===
10/17

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ArrayList<Edge>[] bus = new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            bus[i] = new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val= Integer.parseInt(st.nextToken());
            bus[from].add(new Edge(to,val));
        }

        long[] dis = new long[n+1];
        Arrays.fill(dis, Long.MAX_VALUE);
        dis[1]=0; // 출발점

        for(int i=1;i<n;i++){
            for(int j=1;j<=n;j++){
                for(Edge e : bus[j]){
                    int to = e.to;
                    int val = e.val;
                    if(dis[j] != Long.MAX_VALUE && dis[to] > dis[j]+val){
                        dis[to] = dis[j]+val;
                    }
                }
                
            }
        }

        // 음수 있는지 확인
        for(int i=1;i<=n;i++){
            for(Edge e : bus[i]){
                if(dis[i] != Long.MAX_VALUE && dis[e.to]>dis[i]+e.val){
                    System.out.println(-1);
                    return;
                }
            }
        }

        for(int i=2;i<=n;i++){
            if(dis[i] == Long.MAX_VALUE) System.out.println(-1);
            else System.out.println(dis[i]);
        }
    }

    static class Edge{
        int to; int val;
        Edge(int to, int val){
            this.to = to; this.val=val;
        }
    }
}