798. The Gentlest Route Within a Hop Budget
A courier network has n junctions numbered 1 to n and m two-way roads. Road i joins
a[i] and b[i] and its roughness is w[i].
A parcel travels from junction 1 to junction n. It may be handed over at most H times, so the
route may use at most H roads. The DAMAGE of a route is the roughness of its roughest road.
Print the smallest damage achievable within the hop budget, or -1 if no route of at most H
roads exists at all. When n is 1 the parcel is already there and the answer is 0.
``` roads 1-2 (9), 2-5 (9), 1-3 (1), 3-4 (1), 4-5 (1)
H = 2 -> 9 (only 1-2-5 is short enough) H = 3 -> 1 (1-3-4-5 fits, and every road on it is smooth) ```
## Why this is not problem 1645
Problem 1645 asks for the smallest worst edge on a route with NO limit on how many edges the route
uses, and that version has a clean greedy answer: sort the edges and union them in until the ends
meet. Add a hop budget and that argument dies, because the cheapest bottleneck may only be
reachable by a route that is too long. The example above is exactly that: the roughness-1 roads
connect 1 to 5, and at H = 2 they are useless.
## Why scanning the candidate damages is too slow
A candidate W is easy to test: keep only roads with roughness at most W and ask for the fewest
roads from 1 to n. Since every road counts the same, that is one breadth first search, O(n + m).
The obvious program walks the sorted roughness values in order. There can be 2 * 10^5 distinct
values, so that is 2 * 10^5 searches where 18 would do.
## Why the predicate is monotone
Raising W only adds roads. Adding roads to a graph never lengthens a shortest route, so the
fewest hops from 1 to n is non-increasing in W, and once it drops to H or below it stays
there. Feasible values of W form a suffix, and the answer is the smallest one.
## The bounds, and why they are not 0 and 10^9
The answer is always one of the roughness values that actually appear, because the damage of a
route IS one of its road roughnesses. Sort the distinct values and binary search the INDEX into
that list, which turns log(10^9) steps into log(m) steps and guarantees the reported value is a
real road.
Test the last index before searching. If the whole network still cannot deliver within H hops,
the answer is -1, and checking once removes the need for any other special case.
## The boundary that breaks a careless implementation
H equal to 0. Then only n = 1 succeeds, and a breadth first search that reports success the
moment it enqueues the source without comparing the distance against H gets it wrong.
The second is a network with no roads at all, where the distinct-value list is empty and
values[last] reads off the end.
## Width
Roughnesses reach 10^9, which fits in a signed 32-bit integer, and the algorithm only ever
compares them against the candidate. Hop counts are at most n. Nothing here overflows, which
is a claim worth making explicitly rather than leaving to chance.
## Related problems
Problem 1645 is this question with no hop budget. Problem 790 is the same minimax idea on a grid, where the moves are implicit rather than listed.
## Cost
Time O((n + m) log m). Space O(n + m).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `0 ≤ H ≤ n` - `1 ≤ w ≤ 10^9` - `1 ≤ a, b ≤ n` - roads may repeat
Input
The first line contains three integers n, m and H.
Each of the next m lines contains three integers a, b and w, a road and its roughness.
Output
Print one integer, the smallest possible roughest road on a route from junction 1 to junction n using at most H roads, or -1 when no such route exists. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.