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

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

इसलिए, यदि इनपुट sets = [[0, 4, 4], [0, 5, 12], [2, 6, 9], [4, 8, 10]] और removals = [2, 5, 4, 6, 8] जैसा है, तो आउटपुट 4 होगा।

हल करने के चरण

• N := removals का आकार

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

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

  • [e+1, w] को graph[s] में जोड़ें

• प्रत्येक i, r के लिए इंडेक्स i और आइटम r में removals, करें

  • [i, r] को graph[i + 1] में जोड़ें

• pq := एक नया हीप

• dist := एक नया मैप

• dist[0] := 0

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

  • d, e := हीप pq से सबसे छोटा आइटम हटाएं

  • यदि dist[e] < d शून्येतर है, तो अगले इटरेशन पर जारी रखें

  • यदि e, N के समान है, तो d लौटाएं

  • graph[e] में प्रत्येक nei, w के लिए, करें

    • d2 := d + w

    • यदि d2 < dist[nei] शून्येतर है, तो

      • dist[nei] := d2

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

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