BOJ. Shortest Path (1753)

Solution

The graph is directed, so each edge is stored only in the adjacency list of its source. Dijkstra’s algorithm is valid because all edge weights are nonnegative. The distance array stores the best known distance from the source; when an entry with the smallest tentative distance is removed from the priority queue, relaxing its outgoing edges can only improve neighbors’ distances. If a better route is found later, a new queue entry is added. Older entries are discarded when their distance no longer matches the array.

The queue comparator uses Long.compare rather than subtraction to avoid overflow. Distances use long; unreachable vertices retain INF and are printed as INF, while the source is printed as 0. Parallel edges are all retained, which does not change the result.

With a lazy priority queue, the time complexity is O((V + E) log V) and the 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;
import java.util.PriorityQueue;

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

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

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

    private static class State {
        final int vertex;
        final long distance;

        State(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int vertexCount = input.nextInt();
        int edgeCount = input.nextInt();
        int source = input.nextInt() - 1;

        List<List<Edge>> graph = new ArrayList<>(vertexCount);
        for (int vertex = 0; vertex < vertexCount; vertex++) {
            graph.add(new ArrayList<>());
        }

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

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

        PriorityQueue<State> queue = new PriorityQueue<>(
                (left, right) -> Long.compare(left.distance, right.distance));
        queue.add(new State(source, 0));

        while (!queue.isEmpty()) {
            State current = queue.poll();
            if (current.distance != distance[current.vertex]) {
                continue;
            }

            for (Edge edge : graph.get(current.vertex)) {
                long candidate = current.distance + edge.weight;
                if (candidate < distance[edge.to]) {
                    distance[edge.to] = candidate;
                    queue.add(new State(edge.to, candidate));
                }
            }
        }

        StringBuilder output = new StringBuilder();
        for (long value : distance) {
            output.append(value == INF ? "INF" : value).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();
        }
    }
}