K স্টপের মধ্যে সস্তা ফ্লাইট খুঁজে বের করা C++-এ

সমস্যা বিবরণ

n সংখ্যক সিটি এবং m সংখ্যক ফ্লাইট আছে। প্রতিটি ফ্লাইট u থেকে v যায় খরচ w দিয়ে। সোর্স src থেকে ডেস্টিনেশন dst পর্যন্ত সর্বোচ্চ k স্টপে (অর্থাৎ k+1 এজ) যেতে হলে ন্যূনতম খরচ বের করতে হবে। রুট না থাকলে -1 রিটার্ন করুন।

উদাহরণ

n = 3, ফ্লাইটস = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

আউটপুট: 200 (রুট: 0→1→2, খরচ ১০০+১০০=২০০, ১ স্টপ)

অ্যালগরিদম: ডিকস্ট্রা ভেরিয়েন্ট (Priority Queue + স্টপ লিমিট)

1. গ্রাফ তৈরি করুন: graph[u] = {{v, w}, ...}
2. cost[node][stops] = নোডে stops স্টপে পৌঁছানোর ন্যূনতম খরচ।
3. প্রাইориটি কিউতে {node, stops, cost} রাখুন, মিন-হিপ (কম খরচ আগে)।
4. শুরু: src নোড, ০ স্টপ, ০ খরচ।
5. কিউ খালি না হওয়া পর্যন্ত:
   • টপ এলিমেন্ট পপ করুন।
   • যদি নোড == dst হয় → খরচ রিটার্ন করুন (প্রথমবারের মতো পাওয়া গেলেই ন্যূনতম)।
   • স্টপ বাড়ান। যদি stops > k+1 হয় → স্কিপ করুন।
   • প্রতিটি নেইবারের জন্য রিল্যাক্সেশন করুন: নতুন খরচ কম হলে আপডেট করে কিউতে পুশ করুন।
6. কিউ খালি হলে -1 রিটার্ন করুন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int node, stops, cost;
    Data(int n, int s, int c) : node(n), stops(s), cost(c) {}
};

struct Comparator {
    bool operator()(Data const& a, Data const& b) {
        return a.cost > b.cost; // min-heap
    }
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> cost(n, vector<int>(K + 2, INT_MAX));
        vector<vector<pair<int,int>>> graph(n);
        for (auto& f : flights) {
            graph[f[0]].push_back({f[1], f[2]});
        }

        priority_queue<Data, vector<Data>, Comparator> pq;
        pq.push(Data(src, 0, 0));
        cost[src][0] = 0;

        while (!pq.empty()) {
            Data cur = pq.top(); pq.pop();
            if (cur.node == dst) return cur.cost;
            if (cur.stops > K) continue; // K stops means K+1 edges max

            for (auto& [nei, w] : graph[cur.node]) {
                int newCost = cur.cost + w;
                int newStops = cur.stops + 1;
                if (newCost < cost[nei][newStops]) {
                    cost[nei][newStops] = newCost;
                    pq.push(Data(nei, newStops, newCost));
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << ob.findCheapestPrice(3, flights, 0, 2, 1); // আউটপুট: 200
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(E log V) প্রায়, যেখানে E = ফ্লাইট সংখ্যা, V = সিটি সংখ্যা। স্টপ লিমিটের কারণে প্রতিটি নোড সীমিতবার প্রসেস হয়।
• স্থান জটিলতা: O(V × K + E) — কস্ট টেবিল ও গ্রাফ।