[백준]타임머신(11657)

• 벨만-포드 알고리즘이다.
• 노드갯수가 100~500개일 때 사용한다.
• V개의 정점과 E개의 간선을 가진 가중 그래프에서 특정 출발 정점에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.
• V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. (=시작 정점 A를 포함하여 최대 V개의 정점을 지난다.)
• 특징
  • 음의 가중치를 가지는 간선도 가능하다.
  • 음의 사이클의 존재 여부를 확일 할 수 있다.
  • 최단거리를 구하기 위해서 V-1번 E개의 모든 간선을 확인한다.
  • 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 E개의 간선을 확인한다.
  • 총 연선횟수는 V*E이다. 따라서 시간복잡도는 O(VE)이다.
  • V번째 모든 간선을 확인하였을 때 거리배열이 갱신되었다면, 그래프는 음의 사이클을 가지는 그래프이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int[] dist = new int[501];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(st.nextToken());        // 정점
        int m = Integer.valueOf(st.nextToken());        // 간선
        Edge[] edge = new Edge[m + 1];

        for (int i = 1; i <= n; i++) dist[i] = Integer.MAX_VALUE;

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.valueOf(st.nextToken());    // 시작 도시
            int v = Integer.valueOf(st.nextToken());    // 도착 도시
            int w = Integer.valueOf(st.nextToken());    // 이동 시간
            edge[i] = new Edge(u, v, w);
        }

        dist[1] = 0;                                    // 시작 정점
        for (int i = 1; i < n; i++) {                   // V-1번    
            for (int j = 1; j <= m; j++) {              // V-1번의 E개의 모든 간선 확인
                Edge now = edge[j];
                // 현재 시작도시가 max 값이 아니고 
                // 도착 도시의 이동 시간이 시작도시를 경유해서 이동한 시간 보다 클 때
                if (dist[now.u] != Integer.MAX_VALUE && dist[now.v] > dist[now.u] + now.w) {
                    dist[now.v] = dist[now.u] + now.w;
                }
            }
        }

        for (int j = 1; j <= m; j++) {                  // V번째 모든 간선 확인
            if (dist[edge[j].u] != Integer.MAX_VALUE && dist[edge[j].v] > dist[edge[j].u] + edge[j].w) {
                bw.write("-1");
                bw.flush();
                bw.close();
                return;
            }
        }

        for (int i = 2; i <= n; i++) {
            if (dist[i] != Integer.MAX_VALUE) {
                bw.write(dist[i] + "\n");
            } else {
                bw.write("-1\n");
            }
        }
        bw.flush();
        bw.close();
    }

    public static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}