hardGraphsPure DSA~35 min
Connectivity Queries Under an Edge-Weight Limit
In a weighted network, answer queries of the form: are nodes p and q connected using only links lighter than a given threshold? Process many such queries efficiently.
Problem
Given n nodes and a list edgeList where each edge is [u, v, dist], answer queries where queries[i] = [p, q, limit]: return true if there is a path between p and q using only edges with dist strictly less than limit. Return an array of booleans, one per query.
Input
An integer n, a list edgeList of [u, v, dist], and a list queries of [p, q, limit].
Output
A boolean array, one answer per query.
Constraints
- 2 <= n <= 100000
- 1 <= edgeList.length, queries.length <= 100000
- Edge distances and limits are positive.
Examples
Example 1
Input
n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output
[false,true]
[0,1,2] needs an edge < 2 (none). [0,2,5] uses edges 2 and 4 (< 5).
Example 2
Input
n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output
[true,false]
Only edges below the limit may be used.