백준 11657 - 타임머신

문제

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

풀이

• 음의 가중치가 존재하는 그래프에서 최단 경로를 구하는 문제, 전형적인 벨만-포드 문제
• 1에서 각 정점까지의 최단 거리를 저장한 dist배열을 선언
  - 유의할 점으론 $V=500,\; E=6000$일 때 최대 음수 비용이 $-10000$이므로
  $V\times E\times -10000$의 값이 int 범위를 초과할 수 있음. 따라서 long 타입으로 정의
• $V-1 = N-1$회 동안 각 정점까지의 최단 경로 갱신
• 모든 간선들에 대해 한 번 더 최단 경로 갱신 확인, 이 때 갱신이 가능하면 음의 사이클이 존재하는 경우로 최단 경로를 도출할 수 없는 케이스(-1 출력 후 종료 처리)
• 2~N까지 최단 경로 거리 출력, 무한 값일 경우 도달 불가능한 케이스, -1 출력 처리
• 로직의 시간 복잡도는 $O(VE)=O(NM)=500\times6000$으로 제한 시간 1초를 무난히 통과

코드

import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

    static long[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        dist = new long[N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;

        List<Edge> edges = new ArrayList<>();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());

            edges.add(new Edge(u, v, w));
        }

        for (int i = 0; i < N - 1; i++) {
            for (Edge edge : edges) {
                if (dist[edge.u] != Long.MAX_VALUE && dist[edge.u] + edge.w < dist[edge.v]) {
                    dist[edge.v] = dist[edge.u] + edge.w;
                }
            }
        }

        for (Edge edge : edges) {
            if (dist[edge.u] != Long.MAX_VALUE && dist[edge.u] + edge.w < dist[edge.v]) {
                System.out.println(-1);
                System.exit(0);
            }
        }

        List<String> answer = new ArrayList<>();
        for (int i = 2; i < dist.length; i++) {
            long value = dist[i] == Long.MAX_VALUE ? -1 : dist[i];
            answer.add(String.valueOf(value));
        }
        System.out.print(answer.stream().collect(Collectors.joining("\n")));
        br.close();
    }

    static class Edge {

        int u, v, w;

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

결과