1680. Best Case and Worst Case in One Sweep

A DIRECTED graph of n vertices and m arrows has NO directed cycle, and each arrow carries a weight that may be NEGATIVE. Print TWO numbers on one line: the SMALLEST and then the LARGEST total weight of a route from vertex 1 to vertex n. Print the word none alone if there is no route.

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

Problem 1707 prints the smallest for every vertex. This prints both extremes for one target, and the point is that they come out of the SAME sweep.

## The four 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 weights, and they can decide both answers at once: the lightest copy serves the minimum and the heaviest copy the maximum. unreachable? yes. Print none alone, which is one value where the normal answer is two. When n is 1 the answer is "0 0": one route, of no arrows.

## What most people try first

Two runs, one minimising and one maximising. That works and it is twice the work, and it hides the thing worth noticing: the topological order does not depend on the objective at all. Sort once, then carry two arrays.

The other instinct is Dijkstra for the minimum and Dijkstra with the weights negated for the maximum. Neither half survives: the weights may be negative, so Dijkstra is already wrong for the minimum, and negating them makes the maximum a shortest-path question over negative weights. On a graph with a cycle a longest route would not exist at all. Acyclicity is what makes both questions answerable, and the topological order is the only machinery either one needs.

## One sweep, two arrays

lo[1] = hi[1] = 0, everything else unknown for u in topological order: if u is unknown: skip for each arrow u -> v of weight w: lo[v] = min(lo[v], lo[u] + w) hi[v] = max(hi[v], hi[u] + w)

Note that lo and hi become unknown or known TOGETHER: a vertex is reachable or it is not, and both arrays record exactly the same reachability. So one finiteness test serves both, and testing lo alone is enough to decide whether to print none.

## Why both extremes are correct from one order

The invariant is the same for each. When u is taken from the order, every arrow into u comes from a vertex already processed, so lo[u] and hi[u] are both final. The recurrence then needs only that a route to v is a route to some predecessor plus one arrow, which is true whichever extreme is being taken, because min and max are both associative and both distribute over that decomposition.

That is why the pattern generalises: anything you can combine along a route and extremise at a vertex works here. Problem 1684 does the same sweep with "the minimum arrow on the route" in place of a sum.

## Overflow, computed rather than assumed

A route in an acyclic graph is simple, so it uses at most n - 1 = 49999 arrows of magnitude up to 10^6. Both answers can therefore reach about 5 * 10^10 in magnitude, past the 2147483647 a signed 32 bit integer holds, so both arrays need 64 bits. Note that the two extremes can be very far apart: on the eighth declared test they are -15 and 4.

## Cost

O(n + m), one topological sort and one sweep, with O(n) memory for the two arrays.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `-1000000 ≤ w ≤ 1000000` - The graph has no directed cycle.