BOJ. Get Miminum Cost(2) (11779)

On this page

Problem: BOJ 11779 — Minimum Cost (2)

Given a directed graph with nonnegative edge costs, find the minimum cost from the specified source to destination and print one corresponding route. Keep every directed edge in an adjacency list; parallel edges are valid and need no special handling.

Dijkstra’s algorithm

Maintain distance[v], the smallest source-to-v cost discovered so far, and parent[v], the predecessor used when that distance was last improved. The priority queue holds candidate (vertex, distance) states. Each time the smallest state is removed, discard it if its distance no longer equals distance[vertex]; it was superseded by a better route. Otherwise, relax each outgoing edge and enqueue a new state whenever it improves a neighbor’s distance.

The invariant is that each stored distance is the cost of an actual discovered route, and every queued state represents a candidate route. Because all edge costs are nonnegative, when a state with the globally smallest current distance is removed, no later route through an unprocessed vertex can make it smaller. Relaxation therefore eventually finds the minimum distance to every reachable vertex. Whenever a distance improves, its parent records the preceding vertex on that improving route. Following parents backward from the destination to the source reconstructs a minimum-cost route; reversing that sequence gives the required order. If source and destination are the same, the route naturally contains that single vertex.

Distances and edge costs use long, and the priority queue compares with Long.compare rather than subtraction, avoiding overflow-prone arithmetic in comparisons and distance accumulation. The output is exactly three lines: minimum cost, number of route vertices, and the route itself.

With a binary heap and lazy removal, the time complexity is O((V + E) log(E + 1)) and the space complexity is O(V + E). For a simple graph this is commonly written as O((V + E) log(V + 1)); retaining parallel edges gives the more general bound above.

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 cost;

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

    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();

        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 cost = input.nextLong();
            graph.get(from).add(new Edge(to, cost));
        }

        int source = input.nextInt() - 1;
        int destination = input.nextInt() - 1;

        long[] distance = new long[vertexCount];
        int[] parent = new int[vertexCount];
        Arrays.fill(distance, INF);
        Arrays.fill(parent, -1);
        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.cost;
                if (candidate < distance[edge.to]) {
                    distance[edge.to] = candidate;
                    parent[edge.to] = current.vertex;
                    queue.add(new State(edge.to, candidate));
                }
            }
        }

        List<Integer> path = new ArrayList<>();
        for (int vertex = destination; vertex != -1; vertex = parent[vertex]) {
            path.add(vertex);
            if (vertex == source) {
                break;
            }
        }
        java.util.Collections.reverse(path);

        StringBuilder output = new StringBuilder();
        output.append(distance[destination]).append('\n');
        output.append(path.size()).append('\n');
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) {
                output.append(' ');
            }
            output.append(path.get(i) + 1);
        }
        output.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);

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

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