পাইথনে ফাইনাল টার্গেটে পৌঁছানোর জন্য ন্যূনতম বাস সংখ্যা বের করার প্রোগ্রাম

ধরি আমাদের একটি n x 3 ম্যাট্রিক্স আছে যেখানে প্রতিটি সারিতে তিনটি ফিল্ড [src, dest, id] আছে, অর্থাৎ সেই বাসের রুট src থেকে dest। একটি নতুন বাসে চড়তে এক ইউনিট টাকা লাগে, কিন্তু একই বাসে থাকলে শুধু এক ইউনিট টাকা দিয়ে চলা যায়। লোকেশন ০ থেকে ফাইনাল স্টপ (সর্বোচ্চ লোকেশন) পর্যন্ত বাসে যেতে ন্যূনতম খরচ বের করতে হবে। সমাধান না থাকলে -১ রিটার্ন করুন।

তাই, ইনপুট যদি নিচের ম্যাট্রিক্স হয়, তবে আউটপুট হবে ২, কারণ লোকেশন ০ থেকে বাস ০ চড়ে লোকেশন ৩-এ নামতে পারি। তারপর বাস ১ চড়ে লোকেশন ৫-এ পৌঁছাতে পারি।

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

সমাধানের ধাপগুলো:

start := 0
target := দেয়া ম্যাট্রিক্সের সর্বোচ্চ প্লেস
adj := একটি খালি ম্যাপ
প্রতিটি src, dest, id ইন connections এর জন্য, করুন
- (dest, id) কে adj[src]-এর শেষে ইনসার্ট করুন
hp := (0, start, -1) আইটেম বিশিষ্ট একটি হিপ
seen := একটি খালি ম্যাপ
যখন hp খালি নয়, করুন
- (cost, cur_pos, cur_bus) := হিপ hp-র টপ এলিমেন্ট, এবং টপ ডিলিট করুন
- যদি cur_pos == target, তবে
  - cost রিটার্ন করুন
- যদি cur_bus in seen[cur_pos], তবে
  - নেক্সট ইটেরেশন
- cur_bus কে seen[cur_pos]-এ ইনসার্ট করুন
- প্রতিটি (nex_pos, nex_bus) ইন adj[cur_pos] এর জন্য, করুন
  - next_cost := cost
  - যদি nex_bus != cur_bus, তবে
    - next_cost := next_cost + 1
  - (next_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]]