โปรแกรมหาค่าใช้จ่ายรวมในการส่งสินค้าทั้งหมดใน Python

มี ports adjacency list และ shipments คู่ [i,j] ต้องการส่งจาก i ไป j ค่าใช้จ่าย = ระยะทางสั้นที่สุด หาผลรวมค่าใช้จ่ายทั้งหมด

เช่น ports=[[1,4],[2],[3],[0,1],[]] shipments=[[1,4]] ให้ 4 (เส้นทาง 1→2→3→0→4)

ขั้นตอนการแก้ปัญหา

• สร้าง adjacency matrix dist จาก ports (INF สำหรับไม่เชื่อม)
• Floyd-Warshall หาระยะทางสั้นที่สุดทุกคู่
• รวม dist[i][j] ของทุก shipment ที่เข้าถึงได้

ตัวอย่างโค้ด

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))

อินพุต

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

เอาต์พุต

4