1699. The k Cheapest Routes Through a Pipeline

A DIRECTED graph of n vertices and m arrows has NO directed cycle, and each arrow has a non-negative weight. Print the k smallest total weights of a route from vertex 1 to vertex n, counted WITH REPEATS, in increasing order on one line. Print fewer numbers if fewer routes exist, and the word none if there is no route.

4 vertices, k = 3 1 -> 2 (1) 2 -> 4 (1) 1 -> 3 (1) 3 -> 4 (2) -> 2 3

Only two routes exist, so two numbers are printed.

## The four things that have to be said

directed? yes. self-loops? impossible: a self-loop is a cycle and the input is acyclic. parallel arrows? allowed, and two copies are two routes even at the same weight, so a value may be printed twice. unreachable? yes, and then the word none is printed. Fewer than k routes is not an error; the line is shorter. When n is 1 the only route is the empty one, so the single number 0 is printed.

## Why acyclicity changes the method

Problem 1696 answers the same question on a graph that may have cycles, and has to bound the search by allowing k pops per vertex, because the number of walks is infinite. Here there are no cycles, so the number of routes is finite and every route is simple, and the structure is a straightforward recurrence instead of a search.

That is the general shape of this topic: on a DAG, the topological order replaces the priority queue.

## Merge the k smallest lists of the predecessors

For each vertex keep a SORTED LIST of at most k totals: the k smallest totals of a route from vertex 1 to it.

best[1] = [0] for u in topological order, u not vertex 1: merge, over every arrow (p, u, w), the list { x + w : x in best[p] } sort the merged values and keep the smallest k answer = best[n]

## Why keeping k per vertex is enough

A route to n among the k cheapest has every prefix among the k cheapest routes to that prefix's endpoint. If some prefix were only the (k+1)-th cheapest to a vertex p, then k cheaper routes to p would exist, and each followed by the same remaining arrows would give k cheaper routes to n, so the original would not be among the k cheapest there either.

So truncating each list at k cannot remove an answer, which is the same pruning argument as problem 1696 and the reason both methods are correct.

## Why the lists can be MERGED rather than sorted from scratch

Each incoming list is already sorted, and adding a constant w keeps it sorted. So the vertex's list is a merge of up to deg(u) sorted lists, truncated at k, which a small heap does in O(k log deg) rather than the O(deg * k log(deg * k)) of a full sort. At the stated limits either is fast enough, and the merge is the version that generalises.

## Overflow, computed rather than assumed

A route on a DAG is simple, so it uses at most n - 1 = 19999 arrows of up to 10^9, and a total can reach about 2 * 10^13. The limit of a signed 32 bit integer is 2147483647, so the totals need 64 bits. A single weight of 10^9 fits in 32 bits comfortably.

## Cost

O(m * k log k) time and O(n * k) memory, which at n = 20000, m = 50000 and k = 100 is about 3 * 10^7 operations and two million stored totals.

Constraints - `1 ≤ n ≤ 20000` - `0 ≤ m ≤ 50000` - `1 ≤ k ≤ 100` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000000` - The graph has no directed cycle.