सभी शिपमेंट पूरा करने के लिए कुल लागत ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास 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 := ports सूची से आसन्न मैट्रिक्स
• 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))

इनपुट

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

आउटपुट

4