পাইথনে সব কেনার জন্য সর্বনিম্ন খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের কাছে N আইটেম আছে, যেগুলো 0, 1, 2, …, N-1 হিসেবে চিহ্নিত। তারপর, আমাদেরকে S আকারের একটি 2D তালিকা দেওয়া হয় যাকে সেট বলা হয়। এখানে, আমরা মূল্য সেটের জন্য i-th সেট কিনতে পারি [i,2], এবং আমরা সেট[i, 0] থেকে সেট[i, 1] এর মধ্যে প্রতিটি আইটেম পাই। এছাড়াও, আমাদের কাছে N আকারের একটি তালিকা রয়েছে যাকে অপসারণ বলা হয়, যেখানে আমরা মূল্য অপসারণের জন্য i-th উপাদানের 1টি উদাহরণ ফেলে দিতে পারি[i]। সুতরাং, আমাদের 0 থেকে N-1 সহ প্রতিটি উপাদানের একটি সঠিকভাবে কেনার জন্য সর্বনিম্ন খরচ খুঁজে বের করতে হবে, অথবা যদি এটি করা না যায় তাহলে ফলাফল -1।

সুতরাং, যদি ইনপুট সেটের মত হয় =[ [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 সেটের জন্য, do

  • গ্রাফ[গুলি]

    -এ [e+1, w] যোগ করুন

• প্রতিটি i, সূচী i-এ r এবং অপসারণের ক্ষেত্রে আইটেম r, করুন

  • গ্রাফ[i + 1]

    -এ [i, r] যোগ করুন

• pq :=একটি নতুন গাদা

• dist :=একটি নতুন মানচিত্র

• dist[0] :=0

• pq খালি না থাকার সময়, করুন

  • d, e :=হিপ pq থেকে ক্ষুদ্রতম আইটেমটি সরান

  • যদি dist[e]

    • পরবর্তী পুনরাবৃত্তি চালিয়ে যান

  • e যদি N এর মত হয়, তাহলে

    • d

      ফেরত দিন

  • প্রতিটি nei এর জন্য, w গ্রাফ[e], do

    • d2 :=d + w

    • যদি d2

      • dist[nei] :=d2

      • pq

        এ [d2, nei] যোগ করুন

• রিটার্ন -1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

সংগ্রহ থেকে heapq import defaultdictclass সমাধান:def solve(self, sets, removals):N =len(removals) graph =[[] for _ in range(N + 1)] সেটে s, e, w এর জন্য:গ্রাফ[s].সংযোজন([e + 1, w]) গণনাতে (অপসারণ) i, r-এর জন্য:গ্রাফ[i + 1].অ্যাপেন্ড([i, r]) pq =[[0, 0]] dist =defaultdict(lambda:float("inf")) dist[0] =0 যখন pq:d, e =heapq.heappop(pq) যদি dist[e]  
ইনপুট
 <প্রে>[[0, 4, 4],[0, 5, 12], [2, 6, 9], [4, 8, 10]], [2, 5, 4, 6, 8]

আউটপুট

4