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]的最小值
  • 对于所有形式为[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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告