পাইথনে একটি রোড ট্রিপে আন্তঃদেশীয় ভ্রমণের ন্যূনতম সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি সড়ক ভ্রমণের পরিকল্পনা করতে হবে যাতে বিভিন্ন দেশ থেকে বিভিন্ন শহর পরিদর্শন করা জড়িত থাকে। আমাদের কাছে 'R' রাস্তাগুলির একটি তালিকা রয়েছে, যেখানে প্রতিটি উপাদানকে (x, y, খরচ) হিসাবে বর্ণনা করা হয়েছে। x রাস্তার শুরুর শহর নির্দেশ করে, y রাস্তার গন্তব্য শহরকে নির্দেশ করে এবং খরচ সেই রাস্তা দিয়ে ভ্রমণের খরচ নির্দেশ করে। আমাদের কাছে একটি তালিকা 'C' রয়েছে যেখানে প্রতিটি উপাদান একটি দেশ এবং একটি উপাদান সেই দেশের শহরগুলিকে ধারণ করে। এখন, আমাদের কাছে একটি প্রারম্ভিক শহর 's' এবং একটি গন্তব্য শহর 'e' রয়েছে এবং আমরা উৎস শহর থেকে গন্তব্য শহরে যেতে চাই। এই সমস্ত তথ্যের পরিপ্রেক্ষিতে, ট্রিপটি সম্পূর্ণ করতে আমাদের ন্যূনতম কতগুলি আন্তঃদেশীয় ভ্রমণ করতে হবে এবং ভ্রমণের জন্য ভ্রমণের মোট খরচও খুঁজে বের করতে হবে। আমাদের আউটপুট হিসাবে এই দুটি মান প্রিন্ট করতে হবে।

সুতরাং, যদি ইনপুট হয় R =[[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]], C =[[0], [1], [2, 3]], s =0, e =3, তাহলে আউটপুট হবে (2,5)।

সুতরাং, 0 থেকে 3 পর্যন্ত ভ্রমণ করতে আমরা 0->1->3 পথ ধরি। এই পথে নেওয়া রাস্তাগুলি হল [0, 1, 2], এবং [1, 3, 3]। এইভাবে, মোট দেশ থেকে দেশে ভ্রমণ 2 এবং মোট খরচ 2 + 3 =5।

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

• cont :=একটি নতুন মানচিত্র যেখানে ডিফল্ট মান 0
• প্রতিটি সূচক আইডিএক্স, এবং সি-তে উপাদান আইটেমের জন্য, করুন
  • আইটেমের প্রতিটি k-এর জন্য, করুন
    • cont[k] :=idx
• adj_list :=একটি নতুন মানচিত্র যাতে মান হিসাবে তালিকা রয়েছে
• র জন্য প্রতিটি a, b, wt in R, do
  • যদি cont[a] cont[b] এর মত না হয়, তাহলে
    • wt :=wt + 10 ^ 10
  • adj_list[a] শেষে একটি জোড়া (b, wt) ঢোকান
• দূরত্ব :=একটি নতুন মানচিত্র যেখানে ডিফল্ট মান 10^20
• দূরত্ব[গুলি] :=0
• পরিদর্শন করেছেন :=একটি নতুন সেট
• t :=একটি জোড়া (0, s) ধারণকারী একটি নতুন গাদা
• যখন t খালি নয়, কর
  • জোড়া (d, c) :=স্তূপ থেকে ক্ষুদ্রতম আইটেম পপ করুন
  • যদি c পরিদর্শনে উপস্থিত থাকে, তাহলে
    • পরবর্তী পুনরাবৃত্তির জন্য যান
  • ভিজিটেড সি যোগ করুন
  • প্রতিটি j এর জন্য, adj_list[c] এ wt, do
    • যদি দূরত্ব[j]> d + wt হয়, তাহলে
      • দূরত্ব[j] :=d + wt
      • টি হিপ করতে জোড়া (d + wt, j) ঢোকান
• রিটার্ন পেয়ার ((দূরত্ব[e] / 10 ^ 10) এর ফ্লোর মান), (দূরত্ব[e] মোড 10 ^ 10))

উদাহরণ

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

সংগ্রহ থেকে ইমপোর্ট ডিফল্টডিক্ট ফ্রম heapq import heappush, heappopdef solve(R, C, s, e):idx এর জন্য cont =defaultdict(int), enumerate(C) এ আইটেম:k এর জন্য আইটেম:cont[k] =idx adj_list =defaultdict(list) for a, b, wt in R:if cont[a] !=cont[b]:wt +=10 ** 10 adj_list[a].append((b, wt)) দূরত্ব =defaultdict (lambda:10 ** 20) দূরত্ব[s] =0 পরিদর্শন করা =সেট() t =[(0, s)] যখন t:d, c =heappop(t) যদি c in visited:continue visited.add(c) ) j এর জন্য, adj_list[c]-এ wt:যদি দূরত্ব[j]> d + wt:দূরত্ব[j] =d + wt heappush(t, (d + wt, j)) ফেরত দূরত্ব[e] // 10 * * 10, দূরত্ব[e] % 10 ** 10মুদ্রণ(সমাধান করুন([[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]], [ [0],[1],[2, 3]], 0, 3))

ইনপুট

আউটপুট

(2, 5)