BOJ 타임머신(11657) - Java

문제 - https://www.acmicpc.net/problem/11657

11657번: 타임머신

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

public class Main {

    static int N, M;
    static long[] dist;
    static final int MAX = Integer.MAX_VALUE;
    static class Edge{
        int from, to, cost;
        public Edge(int from, int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }static Edge[] edges;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dist = new long[N+1];
        edges = new Edge[M];
        for (int i = 2; i <= N; i++)
            dist[i] = MAX;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(a, b, c);
        }

        for (int i = 0; i < N-1; i++)
            for (Edge E : edges)
                if(dist[E.from]<MAX)
                    dist[E.to] = Math.min(dist[E.to], dist[E.from]+E.cost);

        if (!isCycle())
            for (int i = 2; i <= N; i++)
                if (dist[i]<MAX)
                    bw.write(dist[i]+"\n");
                else
                    bw.write("-1\n");
        else
            bw.write("-1\n");

        bw.flush();
        bw.close();
        br.close();
    }
    static boolean isCycle(){
        for (Edge E : edges)
            if(dist[E.from]!=MAX && dist[E.from]+E.cost < dist[E.to])
                return true;
        return false;
    }
}

기초 Bellman-Ford 알고리즘이다. 그런데 출력초과로 한참을 벙쪄있었다.

-10,000인 음의 간선이 존재할때, 최대 반복수가 500*6,000이므로 3,000,000*-10,000 이므로 -30,000,000,000이 되어 long타입이 아닌 int타입으로 dist배열을 선언하면 언더플로우가 발생한다.

오버플로우 말고 언더플로우는 처음겪어본다.

아무쪼록 Python을 제외한 언어에서는 문제조건을 보고 자료형에 조금 더 신경써야겠다.