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

मान लीजिए कि हमारे पास पोर्ट नामक सूचियों की एक सूची है, जहां पोर्ट [i] उन पोर्ट की सूची का प्रतिनिधित्व करता है जिनसे पोर्ट i जुड़ा हुआ है। हमारे पास शिपमेंट्स नामक सूचियों की एक और सूची भी है जहां अनुक्रम की प्रत्येक सूची [i, j] जो दर्शाती है कि पोर्ट i से पोर्ट j तक शिपमेंट अनुरोध है। और पोर्ट I से पोर्ट j तक जहाज की लागत दो बंदरगाहों से सबसे छोटे रास्ते की लंबाई है, हमें सभी शिपमेंट को पूरा करने के लिए आवश्यक कुल लागत का पता लगाना होगा।

इसलिए, यदि इनपुट पोर्ट की तरह है =[[1, 4], [2], [3], [0, 1], []] शिपमेंट =[[1, 4]], तो आउटपुट 4 होगा, चूंकि पथ 1 -> 2 -> 3 -> 0 -> 4 से है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=बंदरगाहों का आकार
• dist :=बंदरगाहों की सूची से आसन्न मैट्रिक्स
• जे के लिए 0 से n की सीमा में, करें
  • मैं के लिए 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