ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম যাতে নাগরিকদের পাইথনের একটি বাজারে অ্যাক্সেস থাকে

ধরুন, শহরগুলির সাথে সংযোগকারী n সংখ্যক শহর এবং m রাস্তা রয়েছে। জনগণের নাগরিকদের বাজার দরকার যেখানে তারা তাদের পণ্য কিনতে পারে। এখন, শহরগুলিতে কোনও বাজার নেই, এবং শহরের মধ্যে রাস্তাগুলি নির্মাণাধীন। দুটি শহরের মধ্যে একটি দ্বিমুখী রাস্তা তৈরি করা যেতে পারে যদি (i) শহরে একটি বাজার থাকে; (ii) যেখানে একটি বাজার আছে রাস্তা দিয়ে শহরগুলি পরিদর্শন করা যেতে পারে। একটি রাস্তা নির্মাণের খরচ হল x, এবং একটি বাজার নির্মাণের জন্য y এবং সেগুলো দেওয়া হয়েছে। প্রতিটি শহরের নাগরিকদের বাজারে প্রবেশাধিকার দেওয়ার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে। অ্যারে 'শহর'-এ শহরগুলির সম্পর্কে তথ্য রয়েছে যে শহরগুলিকে রাস্তা দ্বারা সংযুক্ত করা যেতে পারে৷

সুতরাং, যদি ইনপুট হয় n =4, m =3, x =1, y =2, city =[[1, 2], [2, 3], [3, 4]], তাহলে আউটপুট হবে 4.

এখানে, আমরা চারটি শহর দেখতে পাচ্ছি 1, 2, 3 এবং 4। যদি একটি টি সিটি 1 একটি বাজার তৈরি করা হয় এবং (1, 4) এবং (1,3) এর মধ্যে আরও দুটি রাস্তা তৈরি করা হয় তাহলে মোট খরচ হবে 2 + 1 + 1 =4. এটি সর্বনিম্ন খরচ৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি x <=y, তারপর
  • রিটার্ন n * x
• অন্যথায়,
  • adj_list :=উপাদান হিসাবে তালিকা ধারণকারী একটি মানচিত্র
  • শহরের প্রতিটি শহরের জন্য, করুন
    • city1 :=শহর[0]
    • city2 :=শহর[1]
    • adj_list[city1] এর শেষে city2 ঢোকান
    • adj_list[city2] এর শেষে city1 ঢোকান
  • temp :=আকারের একটি নতুন তালিকা (n + 1) মান সত্যের সাথে শুরু করা হয়েছে
  • মান :=0
  • dq :=একটি ডবল শেষ সারি
  • 1 থেকে n + 1 রেঞ্জের cur এর জন্য, করুন
    • যদি temp[cur] অ-শূন্য হয়, তাহলে
      • মান :=মান + x
      • dq-এর একেবারে ডানদিকে cur ঢোকান
      • temp[cur] :=মিথ্যা
      • যখন dq খালি না থাকে, কর
      • প্রতিটি i adj_list[dq-এর বামতম উপাদান নিষ্কাশিত], কর
        • যদি temp[i] অ-শূন্য হয়, তাহলে
          • dq-এর একেবারে ডানদিকে i ঢোকান
          • temp[i] :=মিথ্যা
          • মান :=মান + y
  • রিটার্ন মান

উদাহরণ

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

সংগ্রহ থেকে আমদানি ডিফল্টডিক্ট, dequedef সমাধান(n, m, x, y, city):যদি x <=y:ফেরত n * x else:adj_list =defaultdict(তালিকা) শহরে শহরের জন্য:city1 =city[0 ] city2 =city[1] adj_list[city1].append(city2) adj_list[city2].append(city1) temp =[True] * (n + 1) মান =0 dq =deque() রেঞ্জে cur এর জন্য , n + 1):if temp[cur]:value +=x dq.append(cur) temp[cur] =False while dq:i for adj_list[dq.popleft()]:if temp[i]:dq .append(i) temp[i] =মিথ্যা মান +=y রিটার্ন মান ছাপ /প্রে> 
ইনপুট
 
4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]
 
আউটপুট
 
4