資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算完成所有貨運的總成本
假設我們有一個列表列表，稱為ports，其中ports[i]表示埠i連線到的埠列表。我們還有另一個列表列表，稱為shipments，其中每個列表的序列[i, j]表示從埠i到埠j有一個貨運請求。從埠i到埠j的運輸成本是這兩個埠之間最短路徑的長度，我們需要找到完成所有貨運所需的總成本。
因此，如果輸入類似於ports = [[1, 4],[2],[3],[0, 1],[]] shipments = [[1, 4]]，則輸出將為4，因為路徑是從1 -> 2 -> 3 -> 0 -> 4。
為了解決這個問題，我們將遵循以下步驟：
- n := ports的大小
- dist := 從ports列表生成的鄰接矩陣
- 對於j從0到n，執行：
- 對於i從0到n，執行：
- 對於k從0到n，執行：
- dist[i, k] = dist[i, k]，dist[i, j] + dist[j, k]的最小值
- 對於k從0到n，執行：
- 對於i從0到n，執行：
- 對於所有形式為[i, j]的貨運請求，建立一個列表dist[i,j]，其中dist[i,j]不是無窮大。
- 返回生成的列表的總和。
讓我們看看下面的實現，以更好地理解。
示例
class Solution: def solve(self, ports, shipments): n = len(ports) INF = 10 ** 10 dist = [[INF for _ in range(n)] for _ in range(n)] for i in range(n): dist[i][i] = 0 for i in range(n): for j in ports[i]: dist[i][j] = 1 for j in range(n): for i in range(n): for k in range(n): dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]) return sum(dist[i][j] for i, j in shipments if dist[i][j] != INF) ob = Solution() ports = [[1, 4],[2],[3],[0, 1],[]] shipments = [[1, 4]] print(ob.solve(ports, shipments))
輸入
[[1, 4],[2],[3],[0, 1],[]], [[1, 4]]
輸出
4
更新於: 2020年12月2日
248 次瀏覽
廣告