1684. The Route With the Widest Narrowest Pipe

A DIRECTED graph of n vertices and m arrows has NO directed cycle. Each arrow has a CAPACITY of at least 1, and a route is judged by its SMALLEST capacity, not by a total.

Print the largest possible smallest capacity over all routes from vertex 1 to vertex n. Print none if there is no route, and INF when n is 1, because a route of no arrows has no arrow to be narrowed by.

4 vertices 1 -> 2 (5) 2 -> 4 (6) 1 -> 3 (9) 3 -> 4 (1) -> 5

The route through vertex 3 starts with the widest arrow in the graph and is ruined by its second: its narrowest arrow is 1. The route through vertex 2 is never narrower than 5, and 5 is the answer.

## 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 capacities, and only the widest copy between a pair can ever matter. unreachable? yes. Print none. And n = 1 prints INF, a SECOND word, because the two situations are genuinely different: one has no route and the other has a route with nothing to measure.

## Why two words rather than a number for either case

A capacity is at least 1, so 0 would be available as a sentinel. Using it for both cases would merge them, and they mean opposite things: none says the target cannot be reached, INF says it is reached without passing through any arrow at all. Problem 1645 prints 0 for its single-vertex case because its weights can be 0 and the ambiguity is then unavoidable; here it is avoidable and so it is avoided.

## What most people try first

Maximising the total capacity, or minimising it, and reading off the narrowest arrow of whatever route that finds. Both fail on the first example: the route with the largest total is 1 -> 3 -> 4 at 10, whose narrowest arrow is 1, and the answer is 5. Optimising a sum does not approximate optimising a minimum.

The second instinct is to sort the arrows and add them widest first until 1 and n become connected, which is problem 1645's method turned round. That is correct and it costs O(m log m) and a disjoint-set structure, and on a DAG it is more machinery than the question needs.

## The same sweep with min in place of plus

wide[1] = infinity, everything else unknown for u in topological order: if wide[u] is unknown: skip for each arrow u -> v of capacity c: wide[v] = max(wide[v], min(wide[u], c))

One topological sort, one sweep, O(n + m).

## Why the sweep works for a bottleneck at all

The recurrence of problem 1679 was best[v] = max over arrows of best[u] + w. Here it is wide[v] = max over arrows of min(wide[u], c). What makes either one valid is a decomposition and a monotonicity:

the DECOMPOSITION is that a route to v is a route to some predecessor u plus one arrow, and the value of the whole is a function of the value of the part and the new arrow. For sums that function is +; for bottlenecks it is min.

the MONOTONICITY is that the function is non-decreasing in the value of the part: a wider route into u can only give a wider route into v. So keeping only the best value at u loses nothing, which is what lets one number per vertex be enough.

Anything with those two properties fits this sweep, which is the general lesson: the topological order is indifferent to the objective. max with +, min with +, max with min, and counting with + are all the same pass.

## Where the initial value comes from

wide[1] must be infinity, not 0 and not the widest arrow. The route of no arrows has no narrowest arrow, so nothing limits it yet, and min(infinity, c) is c, which correctly makes the first arrow the only limit so far. Starting at 0 would make every answer 0.

## Magnitude, computed rather than assumed

Nothing is ever added here: every value is min of existing capacities, so the answer is one of the input capacities. A capacity of 10^9 fits in a signed 32 bit integer, whose limit is 2147483647, and so would 2 * 10^9. So 32 bit arithmetic is enough throughout, provided the infinity marker is chosen inside the type rather than by overflowing it.

## Cost

O(n + m), against O(m log m) for the sort-and-union method, with O(n) memory beyond the graph.

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