从Python中的加权图找出可能的最小成本的程序
假设我们有一个称为边的整数的2D列表，它表示无向图。输入中的每一行都表示一条边[u，v，w]，这意味着节点u和v已连接并且该边的权重为w。该图由0到n-1的n个节点组成。
路径成本在此定义为路径中边缘的数量和最大重量的乘积。我们必须找出从节点0到节点n-1的最小成本，或者，如果不存在这样的路径，则将答案声明为-1。
So, if the input is like edges = [ [0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300] ], then the output will be 600
在线示例
让我们看下面的实现以更好地理解-
from collections import defaultdict, deque
class Solution:
def solve(self, edges):
graph = defaultdict(list)
weights = {}
max_weight = 0
N = 0
for u, v, w in edges:
graph[u].append(v)
graph[v].append(u)
weights[u, v] = w
weights[v, u] = w
N = max(N, u + 1, v + 1)
max_weight = max(max_weight, w)
def bfs(root, weight_cap):
target = N - 1
Q = deque([(root, 0, 0)])
visited = [False] * N
visited[0] = True
while Q:
v, d, current_weight = Q.pop()
if v == N - 1:
return d, current_weight
for w in graph[v]:
if visited[w]:
continue
new_weight = weights[v, w]
if new_weight <= weight_cap:
visited[w] = True
zQ.appendleft((w, d + 1, max(current_weight, new_weight)))
return -1, -1
result = float("inf")
while max_weight >= 0:
d, weight = bfs(0, max_weight)
if d >= 0:
result = min(result, d * weight)
max_weight = weight - 1
else:
break
return result if result < float("inf") else -1
ob = Solution()
print (ob.solve( [
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
]))输入值
[ [0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300] ]输出结果
600