1697.Checking Existence of Edge Length Limited Paths
===
###### tags: `Hard`,`Array`,`Graph`
[1697. Checking Existence of Edge Length Limited Paths](https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/)
### 題目描述
An undirected graph of `n` nodes is defined by `edgeList`, where `edgeList[i]` = [$u_i$, $v_i$, $dis_i$] denotes an edge between nodes $u_i$ and $v_i$ with distance $dis_i$. Note that there may be **multiple** edges between two nodes.
Given an array queries, where `queries[j]` = [$p_j$, $q_j$, $limit_j$], your task is to determine for each queries[j] whether there is a path between $p_j$ and $q_j$ such that each edge on the path has a distance **strictly less than** $limit_j$ .
Return *a **boolean array*** `answer`, *where* `answer.length == queries.length` *and the* j^th^ *value of* `answer` *is* `true` *if there is a path for*` queries[j]` *is* `true`, *and* `false` *otherwise.*
### 範例
**Example 1:**
![](https://assets.leetcode.com/uploads/2020/12/08/h.png)
```
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:**
![](https://assets.leetcode.com/uploads/2020/12/08/q.png)
```
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]
Exaplanation: The above figure shows the given graph.
```
**Constraints**:
* 2 <= `n` <= 10^5^
* 1 <= `edgeList.length`, `queries.length` <= 10^5^
* `edgeList[i].length` == 3
* `queries[j].length` == 3
* 0 <= $u_i$, $v_i$, $p_j$, $q_j$ <= `n` - 1
* $u_i$ != $v_i$
* $p_j$ != $q_j$
* 1 <= $dis_i$, $limit_j$ <= 10^9^
* There may be **multiple** edges between two nodes.
### 解答
#### Python
```python=
class Solution:
def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
parents = list(range(n))
ranks = [0] * n
def find(x):
if parents[x] != x:
parents[x] = find(parents[x])
return parents[x]
def union(x, y):
x, y = find(x), find(y)
if x != y:
if ranks[x] < ranks[y]:
parents[x] = y
elif ranks[x] > ranks[y]:
parents[y] = x
else:
parents[y] = x
ranks[x] += 1
ans = [False] * len(queries)
edges = sorted(edgeList, key=lambda x: -x[2])
queries = sorted(enumerate(queries), key=lambda x: x[1][2])
for i, (p, q, limit) in queries:
while len(edges) > 0 and edges[-1][2] < limit:
u, v, _ = edges.pop()
union(u, v)
ans[i] = find(p) == find(q)
return ans
```
> [name=Yen-Chi Chen][time=Mon, May 1, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)