在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：从端口列表的邻接矩阵。
对于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))