1696. The k-th Cheapest Route

A DIRECTED graph has n vertices and m arrows, every weight at least 1. A route is a walk, so vertices and arrows may repeat.

List the totals of all routes from vertex 1 to vertex n in increasing order WITH REPEATS, and print the k-th entry. Print none if fewer than k routes exist.

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

The list is 2, 3 and the second entry is 3. With k = 3 the answer is none, because there are only two routes.

## The four things that have to be said

directed? yes. On an undirected graph there are always infinitely many walks as soon as one arrow exists, and the none case would disappear. self-loops? allowed, and going round one is a different route. parallel arrows? allowed, and two copies are two routes even at the same weight. unreachable? yes, and so is having fewer than k routes. Both print none. When n is 1 the empty route is the only one, so k = 1 answers 0 and any larger k answers none.

## What most people try first

Enumerating routes in increasing order of total with a priority queue holding whole walks, stopping at the k-th arrival at n. That is CORRECT, and it is what the expected answers here were checked against. Its trouble is memory: the queue grows with the number of partial walks, which is exponential, and nothing prunes it.

The second instinct is problem 1694's two values per vertex extended to k values, maintained as sorted lists. That works too and the bookkeeping is fiddly, with a sorted insertion per relaxation.

## Let each vertex be settled k times

The clean version keeps no lists at all. Run Dijkstra, but allow a vertex to be popped up to k times instead of once:

count[v] = 0 for every v push (0, 1) while the heap is not empty and count[n] < k: pop the smallest (d, u) if count[u] == k: discard it count[u] = count[u] + 1 if u == n: this is the count[n]-th smallest total to n for each arrow (u, v, w) with count[v] < k: push (d + w, v)

The k-th time n is popped, the value popped is the answer.

## Why the j-th pop of a vertex is its j-th smallest total

The heap always contains, for every route total not yet popped, at least one entry that is a prefix of it extended by one arrow. Since the heap pops in non-decreasing order and every weight is at least 1, the totals come out sorted, and the j-th time u is popped is the j-th smallest total of a route to u.

The pruning is what makes it finite: a route to n among the k cheapest passes through each intermediate vertex at a total that is among that vertex's k cheapest, because every prefix of a cheap route is cheap. So discarding a pop beyond the k-th at any vertex cannot remove an answer, and the heap holds at most k entries per vertex, which bounds the work at O(k * m log(k * m)).

## The boundary that is easy to miss

Fewer than k routes may exist, and then the heap empties with count[n] below k. That is the none case and it has to be detected by the loop finishing rather than by the heap running dry at some particular moment. A graph with no cycle on the way to n has finitely many routes, which is why the case arises at all on a directed graph.

## Overflow, computed rather than assumed

The k-th total is at most the shortest plus k detours, and a detour costs at most twice the heaviest arrow. The shortest is at most n - 1 = 19999 arrows of 10^9, about 2 * 10^13, and k = 100 detours add at most 2 * 10^11. So the answer stays near 2 * 10^13, past the 2147483647 a signed 32 bit integer holds, and the totals need 64 bits.

## Cost

O(k * m log(k * m)) time and O(k * m) heap entries in the worst case, with O(n) memory for the counters. At k = 100 and m = 50000 that is about 5 * 10^6 heap operations.

Constraints - `1 ≤ n ≤ 20000` - `0 ≤ m ≤ 50000` - `1 ≤ k ≤ 100` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000`