給出一個無向圖最多100000個節(jié)點(diǎn)，每條邊給出相應(yīng)的距離，有最多100000次詢問，每次詢問x和y節(jié)點(diǎn)之間是否存在一條路，路上所有邊的距離都小于（不包含等于）limit。并查集的應(yīng)用，在合并和查找時增加對dis的維護(hù)和判斷
1 #1697
2 #Runtime: 1668 ms (Beats 100%)
3 #Memory: 59.9 MB (Beats 100%)
4
5 class Solution(object):
6 def distanceLimitedPathsExist(self, n, edgeList, queries):
7 """
8 :type n: int
9 :type edgeList: List[List[int]]
10 :type queries: List[List[int]]
11 :rtype: List[bool]
12 """
13 parent = [i for i in range(n)]
14 rank = [i for i in range(n)]
15 def find(x, limit):
16 while x != parent[x]:
17 if dis[x] >= limit:
18 break
19 x = parent[x]
20 return x
21
22 def union(x, y, d):
23 fa = find(x, float('inf'))
24 fb = find(y, float('inf'))
25 if fa != fb:
26 if rank[fa] < rank[fb]:
27 parent[fa] = fb
28 dis[fa] = d
29 else:
30 parent[fb] = fa
31 dis[fb] = d
32 if rank[fa] == rank[fb]:
33 rank[fa] += 1
34
35 def judge(x, y, limit):
36 return find(x, limit) == find(y, limit)
37
38 dis = [0 for _ in range(n)]
39 edgeList.sort(key=lambda x: x[2])
40 for ed in edgeList:
41 union(ed[0], ed[1], ed[2])
42 ans = []
43 for q in queries:
44 ans.append(judge(q[0], q[1], q[2]))
45 return ans