1670. Which Vertices Could Be On the Way

An undirected graph has n vertices and m edges, every weight at least 1. Print, in increasing order, every vertex that lies on AT LEAST ONE cheapest route from vertex 1 to vertex n. Print -1 if there is no route.

Unlike the other reconstruction questions, this answer is unique without any tie-break: a vertex either can be on a cheapest route or it cannot.

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

Both 1 2 4 and 1 3 4 cost 2, so all four vertices qualify. Change 1 - 2 and 2 - 4 to weight 10 and the answer becomes 1 3 4.

## The four things that have to be said

directed? no. Every edge may be walked either way. self-loops? allowed, and irrelevant: they are never on a cheapest route. parallel edges? allowed, at different weights, and only the cheapest copy between a pair can matter. unreachable? yes. Print -1. When n is 1 the answer is the single vertex 1, which lies on the route of no edges.

## What most people try first

Enumerating the cheapest routes and collecting their vertices. The number of cheapest routes can be exponential: a chain of k diamonds, each offering two equal sides, has 2^k of them while having only 3k + 1 vertices. Enumeration is not slow here, it is impossible.

The second instinct is to run the search, keep one cheapest route, and report its vertices. That under-reports, and badly: on the example it prints three vertices where the answer has four.

## Two searches and one equality

Run the search twice, from each end:

ds[v] = cheapest cost from vertex 1 to v dt[v] = cheapest cost from v to vertex n

On an undirected graph dt is just the search from n. Then

v is on some cheapest route exactly when ds[v] + dt[v] == ds[n]

## Why that equality is exactly the condition

Both directions.

If v lies on a cheapest route, split that route at v. The first part is a route from 1 to v, so it costs at least ds[v], and the second costs at least dt[v]. Their sum is ds[n], so ds[v] + dt[v] <= ds[n].

Conversely, gluing a cheapest route from 1 to v onto a cheapest route from v to n gives a WALK from 1 to n of cost ds[v] + dt[v], so ds[n] <= ds[v] + dt[v].

Together, v is on some cheapest route if and only if the two are equal. And when they are, the glued walk is actually a route: weights are at least 1, so a walk of minimum cost cannot repeat a vertex, since cutting the loop out would cost strictly less.

That last step is where the positive weights earn their place. With a zero-weight edge the glued walk could revisit a vertex and still be minimal, and then the equality would hold for vertices no simple cheapest route passes through.

## What this is not

It is not the union of the vertices of SOME cheapest routes, found by running the walk of problem 1663 a few times. And it is not the set of vertices v with ds[v] + dt[v] minimal over all v, which is the same thing said wrongly: the minimum of that sum over all v is ds[n] whenever the target is reachable, so the comparison has to be against ds[n] and not against a running minimum.

## Overflow, computed rather than assumed

A cheapest route is simple, so it uses at most n - 1 = 49999 edges of up to 10^9, and a cost can reach about 5 * 10^13. That is far past the 2147483647 a signed 32 bit integer holds, so ds, dt and their sum need 64 bits. The sum of two of them reaches 10^14, which is still comfortable inside a signed 64 bit integer, whose limit is 9223372036854775807.

## Cost

Two Dijkstra runs, O(m log n), then one pass over the vertices, O(n). Memory is O(n + m).

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