Problem statement

https://binarysearch.com/problems/Shipping-and-Receiving/

Solution

Use Floyd-Warshall algorithm here.

Complexity

It is O(n^3 + p) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, ports, shipments):
        n = len(ports)
        dist = [[0 if i == j else float("inf") for i in range(n)] for j in range(n)]

        for u in range(n):
            for v in ports[u]:
                dist[u][v] = 1

        for k, i, j in product(range(n), repeat = 3):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        return sum(dist[x][y] if dist[x][y] != float("inf") else 0 for x, y in shipments)