資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python實現加權圖最小成本路徑查詢程式
假設我們有一個名為edges的二維整數列表，它表示一個無向圖。輸入中的每一行都表示一條邊[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
為了解決這個問題，我們將遵循以下步驟：
graph := 新建一個對映
weights := 新建一個對映
max_weight := 0
N := 0
對於edges中的每個u, v, w，執行：
將v插入graph[u]的末尾
將u插入graph[v]的末尾
weights[u, v] := w
weights[v, u] := w
N := N, u + 1, v + 1中的最大值
max_weight := max_weight, w中的最大值
result := 無窮大
當max_weight >= 0時，執行：
d, weight := bfs(0, max_weight)
如果d >= 0，則
result := result, d * weight中的最小值
max_weight := weight - 1
否則，
終止迴圈
如果result < 無窮大，則返回result，否則返回-1
定義函式bfs()。這將接收root和weight_cap
target := N - 1
Q := 包含root, 0, 0的雙端佇列
visited := [False] * N
visited[0] := True
當Q不為空時，執行：
v, d, current_weight := 從Q刪除最後一個元素
如果v等於N - 1，則
返回d, current_weight
對於graph[v]中的每個w，執行：
如果visited[w]不為零，則
繼續下一次迭代
new_weight := weights[v, w]
如果new_weight <= weight_cap，則
visited[w] := True
將(w, d + 1, max(current_weight, new_weight))新增到Q的左側
返回-1, -1
示例
讓我們來看下面的實現以更好地理解：
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
665 次瀏覽
