在 Python 中检查是否存在边长受限路径的程序
假设我们有一个无向加权图，其中 n 个节点使用一个 edgeList，其中 edgeList[i] 具有三个参数 (u, v, w) 表示有一条从 u 到 v 的路径，其距离为 w。我们还有另一个查询数组，其中 query[i] 有 (p, q, lim)。该查询试图询问是否存在从 p 到 q 的路径（直接或通过某个其他节点），其距离小于 lim。我们必须为每个查询返回一个包含 True/False 结果的数组。
所以，如果输入像
那么输出将是 [True, False, True]。因为从 1 到 4 我们可以按照路径 1 -> 3 -> 4 花费 11，第二个是错误的，因为我们不能使用小于 3 从 2 到 3，最后一个是真的，因为我们可以从 1使用路径 1 -> 3 -> 2 到 2，成本 14 小于 15。
示例
让我们看看以下实现以更好地理解
def solve(n, edgeList, queries):parent = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]
def find(parent, x):
if parent[x] == x:
return x
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a == b:
return
if rank[a] < rank[b]:
parent[a] = b
elif rank[a] > rank[b]:
parent[b] = a
else:
parent[b] = a
rank[a] += 1
edgeList.sort(key = lambda x: x[2])
res = [0] * len(queries)
queries = [[i, ch] for i, ch in enumerate(queries)]
queries.sort(key = lambda x: x[1][2])
ind = 0
for i, (a, b, w) in queries:
while ind < len(edgeList) and edgeList[ind][2] < w:
union(parent, edgeList[ind][0], edgeList[ind][1])
ind += 1
res[i] = find(parent, a) == find(parent, b)
return res
n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3),]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))
输入
4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)],[(1,4,12),(2,3,3),(1,2,15)]输出结果
[True, False, True]
以上是 在 Python 中检查是否存在边长受限路径的程序 的全部内容， 来源链接： utcz.com/z/363248.html
