1694. The Second Cheapest Different Price

A DIRECTED graph has n vertices and m arrows, every weight at least 1. A ROUTE is a walk: vertices and arrows may be repeated.

Print the second smallest DISTINCT total weight of a route from vertex 1 to vertex n, or the word none if fewer than two different totals exist.

4 vertices 1 -> 2 (1) 2 -> 4 (1) 1 -> 3 (1) 3 -> 4 (2) -> 3

The totals are 2 and 3, so the answer is 3. Change 3 -> 4 to weight 1 and both routes cost 2, there is only one distinct total, and the answer becomes none.

## The four things that have to be said

directed? yes, and that matters here: on an undirected graph you could always step out and back, so a second total would almost always exist and the question would be less interesting. self-loops? allowed. A self-loop of weight w on a vertex of a shortest route gives a second total exactly w larger. parallel arrows? allowed, at different weights, and two copies of DIFFERENT weight are the simplest way to have a second total. unreachable? yes, and so is the case where the target is reachable by only one total. Both print none. When n is 1 the only route is the empty one, costing 0, so there is no second total and the answer is none.

## What most people try first

Running Dijkstra, then running it again with the arrows of the shortest route forbidden one at a time, and taking the best result. That is a correct method for the second shortest SIMPLE path and it is not this question, because routes here are walks: on 1 -> 2 (1), 2 -> 1 (1), 2 -> 3 (1) the second total is 4, reached by bouncing between 1 and 2, and no arrow-removal scheme finds it.

The second instinct is to collect every total into a set and sort it. The number of walks is infinite as soon as the graph has a cycle.

## Keep TWO values per vertex

For each vertex store the smallest total b1[v] and the smallest total STRICTLY GREATER than it, b2[v]. Then run Dijkstra where a vertex may be settled twice:

b1[1] = 0, everything else infinite, b2 infinite everywhere push (0, 1) pop the smallest (d, u); if d > b2[u] it is stale, skip it for each arrow (u, v, w) with nd = d + w: if nd < b1[v]: b2[v] = b1[v]; b1[v] = nd; push (nd, v) else if b1[v] < nd < b2[v]: b2[v] = nd; push (nd, v) answer = b2[n]

The three-way comparison is the whole problem. A value equal to b1[v] is discarded, which is what makes the answer DISTINCT, and problem 1695 is the same code with that one condition relaxed.

## Why two values per vertex are enough

Claim: the second smallest distinct total to v is realised by a route whose prefix to the predecessor u is either the smallest or the second smallest distinct total to u.

Suppose not: the route's prefix to u costs more than b2[u]. Then replacing that prefix by the one costing b2[u] gives a route to v costing less, and still more than b1[v] as long as b2[u] + w > b1[v]; if it is not more, then replacing by b1[u] instead reaches b1[v] and the original was not second smallest at all. Either way a cheaper competitor exists, so the original was not the second smallest. Hence only the top two per vertex can matter, and keeping three or more is wasted work.

## Why the stale check uses b2 and not b1

A popped entry is useful when it equals either of the two stored values, so the test is d > b2[u], not d > b1[u]. Using b1 throws away every second-best arrival and the answer comes out as none on graphs that have one.

## Overflow, computed rather than assumed

The second total is at most the shortest plus twice the heaviest arrow, since one detour round a cycle suffices when a cycle exists. The shortest is at most n - 1 = 19999 arrows of 10^9, about 2 * 10^13, and the detour adds at most 2 * 10^9. 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(m log n) with a constant factor of two, since each vertex is settled at most twice, and O(n) memory for the two arrays.

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