title
给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。
给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。
请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。
示例 1：
输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出：[false,true]
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。
示例 2：
输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出：[true,false]
解释：上图为给定数据。
提示：
2 <= n <= 1051 <= edgeList.length, queries.length <= 105edgeList[i].length == 3queries[j].length == 30 <= ui, vi, pj, qj <= n - 1ui != vipj != qj1 <= disi, limitj <= 109- 两个点之间可能有 多条 边。
solution
并查集 + 离线思维
我们将 \textit{queries}queries 按照 \textit{limit}_jlimit**j 从小到大进行排序，这样所有的询问中对边权的限制就单调递增了。
同时，我们将 \textit{edgeList}edgeList 按照 \textit{dis}_idis**i 从小到大进行排序，这样所有的边权也就单调递增了。
class Solution:
def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
edgeList = sorted(edgeList, key=lambda x: x[2])
# queries = sorted(queries, key=lambda x: x[2])
qids = list(range(len(queries)))
qids = sorted(qids, key=lambda x: queries[x][2])
i = 0
uf = {}
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf.setdefault(a, a)
uf.setdefault(b, b)
ra, rb = find(a), find(b)
if ra != rb:
uf[ra] = rb
def is_connected(a, b):
uf.setdefault(a, a)
uf.setdefault(b, b)
return find(a) == find(b)
i = 0
res = [0] * len(queries)
print(qids)
for qid in qids:
u, v, dis = queries[qid]
while i < len(edgeList) and edgeList[i][2] < dis:
x, y, _ = edgeList[i]
union(x, y)
i += 1
if is_connected(u, v):
res[qid] = True
else:
res[qid] = False
return res