পাইথনে চূড়ান্ত লক্ষ্যে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক বাস খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি n x 3 ম্যাট্রিক্স রয়েছে যেখানে প্রতিটি সারিতে তিনটি ক্ষেত্র রয়েছে [src, dest, id] এর মানে বাসটির src থেকে গন্তব্য পর্যন্ত রুট রয়েছে। একটি নতুন বাসে উঠতে এক ইউনিট টাকা লাগে, কিন্তু একই বাসে থাকলে আমাদের শুধুমাত্র এক ইউনিট দিতে হবে। আমাদের অবস্থান 0 থেকে চূড়ান্ত স্টপেজে (সবচেয়ে বড় অবস্থান) বাসটি নেওয়ার জন্য প্রয়োজনীয় ন্যূনতম খরচ খুঁজে বের করতে হবে। যদি কোন সমাধান না হয় -1 রিটার্ন।

সুতরাং, যদি ইনপুট মত হয়

0	1	0
1	2	0
2	3	0
3	5	1
5	0	2

তাহলে আউটপুট হবে 2, কারণ আমরা অবস্থান 0 থেকে 0 নিতে পারি এবং অবস্থান 3 থেকে বের হতে পারি। তারপরে আমরা অবস্থান 5-এ পৌঁছানোর জন্য বাস 1 নিয়ে যাই।

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

শুরু :=0
লক্ষ্য :=প্রদত্ত ম্যাট্রিক্সের সর্বোচ্চ স্থান
adj :=একটি খালি মানচিত্র
সংযোগে প্রতিটি src, dest, id এর জন্য করুন
- adj[src]
hp :=আইটেম সহ একটি গাদা (0, শুরু, -1)
দেখা হয়েছে :=একটি খালি মানচিত্র
যখন এইচপি খালি না, কর
- (খরচ, cur_pos, cur_bus) :=হিপ এইচপির শীর্ষ উপাদান এবং এইচপি থেকে শীর্ষ মুছে দিন
- যদি cur_pos টার্গেটের মতো হয়, তাহলে
  - ফেরত খরচ
- যদি cur_bus দেখা যায়[cur_pos], তাহলে
  - পরবর্তী পুনরাবৃত্তির জন্য যান
- দেখিত [cur_pos] মধ্যে cur_bus ঢোকান
- প্রত্যেকটির জন্য (nex_pos, nex_bus) adj[cur_pos], do
  - next_cost :=খরচ
  - যদি nex_bus cur_bus এর মত না হয়, তাহলে
    - next_cost :=next_cost + 1
  - ঢোকান (nex_cost, nex_pos, nex_bus) হিপ hp এ
রিটার্ন -1

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

উদাহরণ

from collections import defaultdict
from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, connections):
      start = 0
      target = max(max(y, x) for y, x, _ in connections)

      adj = defaultdict(list)
      for f, t, id in connections:
         adj[f].append((t, id))

      hp = [(0, start, -1)]
      seen = defaultdict(set)

      while hp:
         cost, cur_pos, cur_bus = heappop(hp)
         if cur_pos == target:
            return cost
         if cur_bus in seen[cur_pos]:
            continue
         seen[cur_pos].add(cur_bus)

         for nex_pos, nex_bus in adj[cur_pos]:
            next_cost = cost
            if nex_bus != cur_bus:
               next_cost += 1
            heappush(hp, (next_cost, nex_pos, nex_bus))

      return -1

ob = Solution()
matrix = [
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0],
   [3, 5, 1],
   [5, 0, 2]
]
print(ob.solve(matrix))

ইনপুট

matrix = [[0, 1, 0],  
[1, 2, 0],  
[2, 3, 0],  
[3, 5, 1],  
[5, 0, 2]]