BOJ. Time Machine (11657)

Approach

The graph is directed and may contain negative edge weights, so Dijkstra’s algorithm is not suitable. Bellman–Ford stores the best known distance from vertex 1 and relaxes every edge up to V - 1 times. Any shortest path without a cycle uses at most V - 1 edges; stopping when a pass makes no changes avoids unnecessary work.

Initialize all distances to a true long infinity value and set only vertex 1 to zero. Before relaxing an edge, skip it if its source is still infinite. This both prevents arithmetic on the sentinel and ensures that an unreachable negative cycle cannot be mistaken for a cycle reachable from vertex 1. After the passes, one more scan detects a reachable negative cycle: if any edge can still be relaxed from a finite distance, print -1. Otherwise, print the distances to vertices 2 through N, using -1 for unreachable vertices.

Bellman–Ford supports negative edges. Its worst-case time complexity is O(VE) and its space complexity is O(V + E).

Problem link

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    private static final long INF = Long.MAX_VALUE / 4;

    private static class Edge {
        final int from;
        final int to;
        final long weight;

        Edge(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int vertexCount = input.nextInt();
        int edgeCount = input.nextInt();
        List<Edge> edges = new ArrayList<>(edgeCount);

        for (int i = 0; i < edgeCount; i++) {
            int from = input.nextInt() - 1;
            int to = input.nextInt() - 1;
            long weight = input.nextLong();
            edges.add(new Edge(from, to, weight));
        }

        long[] distance = new long[vertexCount];
        Arrays.fill(distance, INF);
        distance[0] = 0;

        for (int pass = 0; pass < vertexCount - 1; pass++) {
            boolean changed = false;
            for (Edge edge : edges) {
                if (distance[edge.from] == INF) {
                    continue;
                }
                long candidate = distance[edge.from] + edge.weight;
                if (candidate < distance[edge.to]) {
                    distance[edge.to] = candidate;
                    changed = true;
                }
            }
            if (!changed) {
                break;
            }
        }

        for (Edge edge : edges) {
            if (distance[edge.from] != INF
                    && distance[edge.from] + edge.weight < distance[edge.to]) {
                System.out.println(-1);
                return;
            }
        }

        StringBuilder output = new StringBuilder();
        for (int vertex = 1; vertex < vertexCount; vertex++) {
            output.append(distance[vertex] == INF ? -1 : distance[vertex]).append('\n');
        }
        System.out.print(output);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int length;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        private long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            boolean negative = c == '-';
            if (negative) {
                c = read();
            }

            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return negative ? -value : value;
        }

        private int nextInt() throws IOException {
            return (int) nextLong();
        }
    }
}