用 Python 编写程序，用于确定无向图中的顶点是否具有成本更低的路径

pythonserver side programmingprogramming更新于 2025/12/14 1:16:17

假设，我们得到一个加权无向图。我们必须实现一个函数查询，该查询以两个顶点和一个成本"限制"作为输入，并检查是否存在比输入给出的成本更低的成本路径。如果存在路径，则返回 true，否则返回 false。

因此，如果输入如下

查询为 (0, 2, 10)、(3, 1, 30)、(4, 3, 30)。

则输出为

False
True
True

第一个查询的结果为 False，因为成本为 10 的顶点 0 到 2 之间没有路径。

第二个查询的结果为 True，因为成本为 1 的顶点 3 到 1 之间存在路径10，小于 30。

第三个查询的结果为 True，因为顶点 4 到 3 之间存在一条路径，其成本为 30，等于 30。

为了解决这个问题，我们将遵循以下步骤 −

权重 := 包含图中不同权重的列表
连接 := 包含权重连接的列表
定义函数 query()。这将需要 p、q、limit
- index := 权重中的位置，此处 limit 可以插入到保持排序顺序的左侧
- 如果 index 与 0 相同，则
  - 返回 False
- 如果 connections[index-1, p] 与 connections[index-1, q] 相同，则返回 True

示例

让我们看看下面的实现以便更好地理解 −

import bisect
class Solution(object):

   def __init__(self, n, edgeList):
      def find(node):
         if parent[node]!=node:
            parent[node] = find(parent[node])
         return parent[node]

      def union(x,y):
         parent[find(y)] = find(x)
         return

      parent = {i:i for i in range(n)}
      edgeList.sort(key = lambda x:x[2])
      self.connections = []
      self.weights = []
      for index,(i,j,weight) in enumerate(edgeList):
         union(i,j)
         if index!=len(edgeList)-1 and weight == edgeList[index+1][2]:
            continue
         self.weights.append(weight)
         self.connections.append([find(i) for i in parent])


   def query(self, p, q, limit):
      index = bisect.bisect_left(self.weights,limit)
      if index==0:
         return False
      return self.connections[index-1][p] == self.connections[index-1][q]

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))

输入

ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))