1665. The Route When Some Arrows Pay You

A DIRECTED graph has n vertices and m arrows whose weights may be NEGATIVE. Every directed cycle is guaranteed to have strictly positive total weight, so a cheapest route exists whenever the target is reachable.

Print the vertices of a cheapest route from vertex 1 to vertex n, in order, separated by single spaces, or -1 if there is no route. Among all cheapest routes, print the one whose sequence of vertex numbers is smallest in dictionary order.

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

The route 1 2 4 costs 2 and the route 1 3 2 4 costs 0, so the longer one is cheaper. Problem 388 is the version where that cannot happen.

## The four things that have to be said

directed? yes. An arrow may be followed only forwards. self-loops? a self-loop is a cycle, so its weight is positive, and it is never on a cheapest route. parallel arrows? allowed, at different weights, and the cheaper copy wins. unreachable? yes. Print -1. When n is 1 the answer is the single line "1". No input here is unbounded below, because every cycle has positive weight; problem 1641 is the version that is.

## What most people try first

Bellman-Ford with a parent recorded on every successful relaxation, then follow parents back from n. That is the textbook move and it is where the real bug in this problem lives.

A parent written during relaxation records the best route KNOWN AT THAT MOMENT. Later rounds lower dist for vertices in the middle of the route, and the parent of a vertex further along is not rewritten unless that vertex itself improves. So the parent chain can mix rounds, and with negative weights it can even contain a cycle, which turns the read-back into an infinite loop rather than a wrong answer.

The second attempt, Dijkstra, is wrong for a different and well known reason: it settles a vertex and never revisits it, so an arrow of weight -3 arriving late is discarded. On the example above it answers 2.

## Rebuild the route from the FINAL distances

Do not record parents at all. Run Bellman-Ford on the REVERSED graph from n, giving distT[v], the cheapest cost from v to n. Then walk forwards:

u = 1, print u while u != n: among arrows (u, v, w) with w + distT[v] == distT[u] and v not already used, take the SMALLEST v print v, u = v

Every value read is final, so nothing can be stale. The test for an arrow being usable is an equality between converged numbers, which is the difference between this and a parent written mid-search.

## Why the walk is finite, and why it needs the "not already used" guard

With non-negative weights distT strictly decreases along the walk, which alone rules out repeats. A negative arrow can RAISE distT, so that argument is gone here. What replaces it is the guarantee that every cycle has positive weight: a cheapest route is therefore simple, because cutting any cycle out of a walk would strictly reduce its cost. Carrying a used-vertex set makes the implementation match that argument instead of relying on it silently.

## Cost

Bellman-Ford is O(n * m), which at n = 1000 and m = 5000 is 5 * 10^6 relaxations. The walk is O(n + m). A cheapest route has at most 999 arrows of magnitude at most 1000, so a total stays within 10^6 and a 32 bit integer is ample, provided the infinity marker cannot wrap when a negative weight is added to it. Guard the relaxation with a finiteness test instead, which is cleaner.

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ 5000` - `1 ≤ u, v ≤ n` - `-1000 ≤ w ≤ 1000` - Every directed cycle has strictly positive total weight.