{leetcode}/problems/checking-existence-of-edge-length-limited-paths/[LeetCode - 1697. Checking Existence of Edge Length Limited Paths ^]
An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [u<sub>i</sub>, v<sub>i</sub>, dis<sub>i</sub>] denotes an edge between nodes u<sub>i</sub> and v<sub>i</sub> with distance dis<sub>i</sub>. Note that there may be multiple edges between two nodes.
Given an array queries, where queries[j] = [p<sub>j</sub>, q<sub>j</sub>, limit<sub>j</sub>], your task is to determine for each queries[j] whether there is a path between p<sub>j</sub> and q<sub>j</sub><sub> </sub>such that each edge on the path has a distance strictly less than limit<sub>j</sub> .
Return a boolean array _`answer`, where `answer.length == queries.length` _and the _`jth` _value of _`answer` _is _`true` if there is a path for `queries[j]` is `true`, and `false` otherwise_.
Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/h.png" style="width: 267px; height: 262px;" />
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: <img alt="" src="https://assets.leetcode.com/uploads/2020/12/08/q.png" style="width: 390px; height: 358px;" />
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.
Constraints:
-
2 ⇐ n ⇐ 105 -
1 ⇐ edgeList.length, queries.length ⇐ 105 -
edgeList[i].length == 3 -
queries[j].length == 3 -
0 ⇐ u<sub>i</sub>, v<sub>i</sub>, p<sub>j</sub>, q<sub>j</sub> ⇐ n - 1 -
u<sub>i</sub> != v<sub>i</sub> -
p<sub>j</sub> != q<sub>j</sub> -
1 ⇐ dis<sub>i</sub>, limit<sub>j</sub> ⇐ 109 -
There may be multiple edges between two nodes.