1697. The k Cheapest Different Prices

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.

Print the k smallest DISTINCT total weights of a route from vertex 1 to vertex n, in increasing order on one line. Print fewer than k numbers if fewer distinct totals exist, and the word none if there is no route at all.

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

Only two distinct totals exist, so two numbers are printed rather than three. Problem 1696 counts repeats and prints one number; this one counts values and prints a list.

## The four things that have to be said

directed? yes. An undirected graph would have infinitely many walks from the first arrow onwards. self-loops? allowed. A self-loop of weight w on a route adds a distinct total every time it is taken. parallel arrows? allowed. Two copies of the SAME weight give one distinct total, not two, which is the difference from problem 1696. unreachable? yes, and then the word none is printed. Fewer than k distinct totals is not an error: the line is simply shorter. When n is 1 the only total is 0, so one number is printed whatever k is.

## What most people try first

Problem 1696's method run k times with increasing indices, collecting the answers and removing duplicates. That gives at most k DISTINCT values only when there are no ties at all; with ties it returns fewer than k distinct numbers and there is no way to ask for more, because the index that would produce the next distinct value is not known in advance.

The second instinct is to run problem 1696 with a much larger k, say k * k, and hope. That is a guess rather than a bound.

## Deduplicate inside the search

Keep problem 1696's rule of settling each vertex up to k times, and add one condition: a popped value that EQUALS the previous value popped for that same vertex is discarded without using up one of its k settlements.

count[v] = 0, last[v] = none push (0, 1) while the heap is not empty and fewer than k answers found: pop the smallest (d, u) if d == last[u]: discard, this is a repeat if count[u] == k: discard last[u] = d, count[u] = count[u] + 1 if u == n: record d as the next answer for each arrow (u, v, w) with count[v] < k: push (d + w, v)

## Why comparing with the PREVIOUS value is enough

The heap pops in non-decreasing order, so all the entries carrying one value for a vertex are popped consecutively, with nothing of a different value in between. A single remembered value per vertex therefore catches every duplicate, and no set is needed.

That is the whole saving, and it depends on the pops being ordered. A method that relaxed in an arbitrary order would need a set per vertex.

## Why k distinct values per vertex still suffice

The pruning argument of problem 1696 carries over. A route to n whose total is among the k smallest distinct values has every prefix among the k smallest distinct values at its endpoint, since k strictly smaller distinct prefix totals would give k strictly smaller distinct totals at n. So counting distinct settlements rather than all settlements prunes the right thing.

## Overflow, computed rather than assumed

The k-th distinct total is at most the shortest plus k detours of 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 2 * 10^11. The limit of a signed 32 bit integer is 2147483647, so the totals need 64 bits.

## Cost

O(k * m log(k * m)) time and O(k * m) heap entries at worst, with O(n) memory for the counters and the remembered values.

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