794. Journeys Under a Weight Limit
A freight network has n stations numbered 1 to n and m two-way links. Link i joins
a[i] and b[i] and can carry axles of weight up to w[i], exclusive: a lorry of weight x
may use the link only when x < w[i].
Then q journeys are asked about. Journey j gives a start u, a destination v and a weight
limit[j], and asks whether a lorry of that weight can get from u to v using links it is
allowed on. The lorry may pass through any stations on the way.
Print Yes or No for each journey, in the order asked.
links 1-2 (2), 2-3 (4), 3-1 (8), 2-1 (16)
journey 1 to 2 under 2 -> No (the 2 link needs weight strictly under 2)
journey 1 to 3 under 5 -> Yes (1-2 then 2-3, both under 5)
## Why the obvious answer is too slow, and what it suggests
Each journey on its own is a search: delete the links that are too weak, then ask whether u and
v are connected. That is O(n + m) per journey, so q journeys cost O(q * (n + m)), which
at the limits is 3 * 10^10 steps.
A student who has just met binary search on the answer reaches for it here and it does not help, because the question is not "find the threshold" but "test this threshold", and each test already costs a full search. What DOES carry over is the reason binary search worked at all: the answer to a threshold question is monotone in the threshold.
## The monotone structure, and how to use it once for all the journeys
Raising the limit only ADDS links. The set of links a lorry may use grows as the limit grows, so connectivity between two stations, once established, is never lost.
That means the journeys do not have to be answered in the order they were asked. Sort the links by capacity and the journeys by limit, then sweep once:
for each journey in increasing order of limit:
add every link whose capacity is strictly below that limit
answer Yes when u and v are now in the same group
Each link is added exactly once across the whole sweep. Union-find keeps "same group" at almost constant cost, and the answers are put back in the asked order at the end.
This is the offline twin of binary search on the answer: instead of one question narrowing a range by halving, many questions are answered by walking the range once in order.
## The boundary that breaks a careless implementation
The comparison is STRICT. A link of capacity w is usable at limit L only when w < L, so the
sweep must add links while w < L, not while w <= L. The first sample journey answers No
precisely because a capacity of 2 is not enough at a limit of 2.
The second is a journey whose start equals its destination. It is always Yes, even when no link
touches that station, which a search that requires at least one step gets wrong.
## Width
Capacities reach 10^9 and a limit may be 10^9 + 1. Both sit inside a signed 32-bit
integer, whose top is 2147483647, and nothing here is added or multiplied, so 64 bits are
not needed. Read the constraint rather than guessing: one more zero on either bound and it would
be.
## Related problems
Problem 1645 asks for the smallest worst link on one route, which is the smallest limit that would
turn a No into a Yes here. Problem 987 sweeps the same union-find forwards in time to find
the first moment a whole network connects.
## Cost
Time O(m log m + q log q + (m + q) * inverse Ackermann). Space O(n + m + q).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 200000` - `1 ≤ q ≤ 100000` - `1 ≤ w ≤ 10^9` - `1 ≤ limit ≤ 10^9 + 1` - links may repeat and may join a station to itself
Input
The first line contains three integers n, m and q.
Each of the next m lines contains three integers a, b and w, a link and its capacity.
Each of the next q lines contains three integers u, v and limit, one journey.
Output
Print q lines. Line j holds Yes if journey j is possible and No if it is not, spelled exactly like that, one word per line and nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.