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

मान लीजिए, हमारे पास N आइटम हैं, जिन्हें 0, 1, 2,…, N-1 के रूप में चिह्नित किया गया है। फिर, हमें आकार S की एक 2D सूची दी जाती है जिसे सेट कहा जाता है। यहां, हम मूल्य सेट [i, 2] के लिए i-th सेट खरीद सकते हैं, और हम सेट [i, 0] से सेट [i, 1] के बीच प्रत्येक आइटम प्राप्त करते हैं। इसके अलावा, हमारे पास आकार N की एक सूची है जिसे रिमूवल कहा जाता है, जहां हम मूल्य हटाने के लिए i-वें तत्व के 1 उदाहरण को फेंक सकते हैं [i]। इसलिए, हमें 0 से लेकर N-1 तक प्रत्येक तत्व में से एक को खरीदने के लिए न्यूनतम लागत का पता लगाना होगा, या यदि ऐसा नहीं किया जा सकता है तो परिणाम -1 है।

So, if the input is like sets = [
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
]

निष्कासन =[2, 5, 4, 6, 8], तो आउटपुट 4 होगा।

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

• N :=निष्कासन का आकार

• ग्राफ:=आकार के लिए एक नया मैट्रिक्स (N + 1) x (N + 1)

• सेट में प्रत्येक s, e, w के लिए करें

  • [e+1, w] को ग्राफ़ में जोड़ें[s]

• प्रत्येक i के लिए, r अनुक्रमणिका i में और आइटम r निष्कासन में, करें

  • [i, r] को ग्राफ़ में जोड़ें[i + 1]

• pq :=एक नया ढेर

• जिला:=एक नया नक्शा

• जिला [0] :=0

• जबकि pq खाली नहीं है, करें

  • d, e :=हीप pq से छोटी से छोटी वस्तु को हटा दें

  • अगर dist[e]

    • अगला पुनरावृत्ति जारी रखें

  • यदि e, N के समान है, तो

    • वापसी d

  • प्रत्येक नी के लिए, ग्राफ़ में w[e], do

    • d2 :=d + w

    • अगर d2

      • जिला [नेई] :=d2

      • pq में [d2, nei] जोड़ें

• वापसी -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import heapq
from collections import defaultdict
class Solution:
   def solve(self, sets, removals):
      N = len(removals)
      graph = [[] for _ in range(N + 1)]
      for s, e, w in sets:
         graph[s].append([e + 1, w])
      for i, r in enumerate(removals):
         graph[i + 1].append([i, r])
      pq = [[0, 0]]
      dist = defaultdict(lambda: float("inf"))
      dist[0] = 0
      while pq:
         d, e = heapq.heappop(pq)
         if dist[e] < d:
            continue
         if e == N:
            return d
         for nei, w in graph[e]:
            d2 = d + w
            if d2 < dist[nei]:
               dist[nei] = d2
               heapq.heappush(pq, [d2, nei])
      return -1

ob = Solution()
print (ob.solve([
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
], [2, 5, 4, 6, 8]))

इनपुट

[[0, 4, 4],
[0, 5, 12],
[2, 6, 9],
[4, 8, 10]], [2, 5, 4, 6, 8]

आउटपुट

4