পাইথনে শিপমেন্ট সম্পন্ন করার মোট খরচ বের করার প্রোগ্রাম

পোর্টের সংযোগ তালিকা ports এবং শিপমেন্ট রিকোয়েস্ট shipments দেওয়া আছে। দুটি পোর্টের মধ্যে সবচেয়ে ছোট পথের দৈর্ঘ্য হলো খরচ। সকল শিপমেন্টের মোট খরচ বের করুন।

উদাহরণ: ports = [[1,4],[2],[3],[0,1],[]], shipments = [[1,4]] → আউটপুট ৪ (পথ ১→২→৩→০→৪)।

সমাধানের ধাপগুলো:

ফ্লয়েড-ওয়ার্শাল অ্যালগরিদম দিয়ে সকল জোড়ার সর্বনিম্ন দূরত্ব বের করুন।
শিপমেন্টের জন্য দূরত্ব যোগ করুন।

উদাহরণ

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