Chương trình tính tổng chi phí vận chuyển tất cả lô hàng bằng Python

Cho danh sách kề ports (cảng i kết nối đến các cảng trong ports[i]) và danh sách shipments (yêu cầu từ i đến j). Chi phí = độ dài đường đi ngắn nhất. Tính tổng chi phí tất cả lô hàng.

Ví dụ: ports=[[1,4],[2],[3],[0,1],[]], shipments=[[1,4]] → 4 (đường 1→2→3→0→4).

Giải thuật

• Xây dựng ma trận kề dist (INF cho không liên thông, 0 cho đường chéo, 1 cho cạnh trực tiếp).
• Chạy Floyd-Warshall tính đường đi ngắn nhất mọi cặp.
• Tổng chi phí = tổng dist[i][j] cho các (i,j) trong shipments nếu có đường đi.

Ví dụ minh họa

class Solution:
    def solve(self, ports, shipments):
        n = len(ports)
        INF = 10**10
        dist = [[INF]*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))

Đầu vào

[[1,4],[2],[3],[0,1],[]], [[1,4]]

Đầu ra

4