1707. Cheapest Route When the Jobs Cannot Repeat

A DIRECTED graph with n vertices and m arrows has NO directed cycle. Each arrow carries a weight which may be NEGATIVE. Print, for every vertex, the smallest total weight of a route from vertex 1 to it, or the word UNREACHABLE if no route exists.

4 vertices, 1->2 (5), 1->3 (2), 2->4 (1), 3->4 (7) -> 0 5 2 6 4 vertices, 1->2 (10), 2->3 (-20), 3->4 (5) -> 0 10 -10 -5 5 vertices, 1->2 (4), 4->5 (3) -> 0 4 UNREACHABLE UNREACHABLE UNREACHABLE

Vertex 1 is always at distance 0, since the route that goes nowhere costs nothing.

## The three things that have to be said

directed? yes. self-loops? impossible: a self-loop is a cycle and the input is acyclic. parallel arrows? allowed, at different prices, and the cheapest copy wins. disconnected? allowed. Anything vertex 1 cannot reach prints UNREACHABLE, including vertices that arrows do touch but only point away from vertex 1.

## What most people try first

Dijkstra's algorithm. It is the right instinct for a shortest-route question and it is wrong here, because it settles a vertex the moment that vertex has the smallest tentative distance and never revisits it. A negative arrow leaving a settled vertex can still lower a distance that Dijkstra has already frozen. Problem 388 is the version where Dijkstra is correct, and the difference between the two problems is exactly the sign of the weights.

The second instinct is Bellman-Ford, which IS correct here: n - 1 rounds over every arrow. It is also O(n m), which at the stated limits is 4 * 10^10 relaxations, and it is what the expected answers here were checked against.

## The acyclicity buys a single pass

Relax the arrows in a topological order of the vertices.

dist[1] = 0, everything else unknown for u in topological order: if dist[u] is unknown: skip for each arrow u -> v with weight c: dist[v] = min(dist[v], dist[u] + c)

## Why one pass is enough

Take any vertex v and the cheapest route to it, say 1 = x0 -> x1 -> ... -> xk = v. Every arrow of that route points forwards in the topological order, so the vertices appear in the order x0, x1, ..., xk as the loop runs. By induction, when the loop reaches xi its distance is already at most the cost of the route's prefix: true at x0, and the step from xi to xi+1 is a relaxation the loop performs while standing at xi, before it ever reaches xi+1. So when the loop reaches v, dist[v] is already at most the cost of the cheapest route, and it is never less because every value assigned is the cost of some real route.

Nothing in that argument cares about the sign of the weights. What it uses is that a route visits vertices in topological order, which is why the same single pass fails on a graph with a cycle: there the route can go backwards.

## Why UNREACHABLE is not the same as a very large number

It is tempting to set unknown distances to a big sentinel and print it. Then an arrow of weight -10^9 leaving an unreachable vertex produces sentinel - 10^9, which is still large but no longer equal to the sentinel, and the vertex prints a number instead of UNREACHABLE. The 3 2 test, whose arrows all point towards vertex 1, is there for this: a route must START at vertex 1, and a vertex touched by arrows can still be unreachable. Keep a reached flag, or guard every relaxation with "is u reached".

## Overflow

A weight is up to 10^9 in magnitude and a route can use n - 1 arrows, so a distance reaches 2 * 10^14 in magnitude. A signed 32 bit integer holds -2147483648 to 2147483647, so a single weight of 10^9 fits inside it and so does 2000000000, but the SUM does not. The declared case of five arrows of -10^9 gives -5000000000, which a 32 bit accumulator reports as -705032704.

## Cost

Time O(n + m): one Kahn pass, each arrow relaxed once. Space O(n + m). Compare Bellman-Ford's O(n m) and Dijkstra's O(m log n), which is both slower than this and wrong on these weights.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `-1000000000 ≤ c ≤ 1000000000` - the graph has no directed cycle, so no self-loop can occur - the same arrow may be listed more than once, at different weights - the graph may be disconnected - a distance can reach `2 * 10^14` in magnitude, so it needs 64 bits