#1697
Checking Existence of Edge Length Limited Paths
expert · 1110 · lc hard +32 · verified · 63.2% accepted · 2,102 likes · top 65%
Description
An undirected graph with n nodes is described by edgeList, where edgeList[i] = [ui, vi, disi] represents an edge between ui and vi with weight disi. Multiple edges between the same pair of nodes are allowed.
For each queries[j] = [pj, qj, limitj], determine whether there is a path from pj to qj where every edge weight is strictly less than limitj.
Return a boolean array answer where answer[j] is true if such a path exists and false otherwise.
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]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.
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]
Explanation: The above figure shows the given graph.
Code
1
2
3