C++-এ K স্টপের মধ্যে সস্তার ফ্লাইট

ধরুন আমাদের n শহর আছে m ফ্লাইট দ্বারা সংযুক্ত। প্রতিটি ফ্লাইট u থেকে শুরু হয় এবং একটি মূল্য w সহ v এ পৌঁছায়। যদি আমাদের সমস্ত শহর এবং ফ্লাইট থাকে, একত্রে শুরুর শহর src এবং গন্তব্য dst সহ, এখানে আমাদের কাজ হল src থেকে dst পর্যন্ত k স্টপ সহ সবচেয়ে সস্তা মূল্য খুঁজে পাওয়া। যদি এমন কোন রুট না থাকে, তাহলে ফিরুন -1।

সুতরাং, যদি ইনপুট n =3, edges =[[0,1,100],[1,2,100],[0,2,500]], src =0, dst =2, k =1 এর মত হয়, তাহলে আউটপুট হবে 200

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

• ডেটা নামে একটি ডেটা স্ট্রাকচার তৈরি করুন, এটি নোড, ডিস্ট এবং ভ্যাল

  ধরে রাখতে পারে

• একটি 2D অ্যারে খরচ সংজ্ঞায়িত করুন

• খরচ :=অর্ডারের একটি 2D অ্যারে (n + 1) x (K + 10) এটিকে অসীম দিয়ে পূরণ করুন

• একটি 3D অ্যারে গ্রাফ সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i <ফ্লাইটের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • u :=ফ্লাইট[i, 0]

  • v :=ফ্লাইট[i, 1]

  • গ্রাফ[u]

    -এর শেষে { v, flights[i, 2] } সন্নিবেশ করুন

• একটি অগ্রাধিকার সারি q

  সংজ্ঞায়িত করুন

• q

  -এ ডেটা(src, 0, 0) সন্নিবেশ করান

• খরচ[src, 0] :=0

• উত্তর :=-1

• যখন (q খালি নয়), −

  করুন

  • temp :=q

    এর শীর্ষ উপাদান

  • curr :=temp.node

  • q

    থেকে উপাদান মুছুন

  • dist :=temp.dist

  • যদি curr dst এর মত হয়, তাহলে −

    • রিটার্ন temp.cost

  • (1 দ্বারা দূরত্ব বাড়ান)

  • যদি dist> K + 1 হয়, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার[curr], আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

    • প্রতিবেশী :=গ্রাফ[curr, i, 0]

    • যদি খরচ[প্রতিবেশী, জেলা]> খরচ[curr, dist - 1] + graph[curr, i, 1], তাহলে −

      • খরচ[প্রতিবেশী, জেলা] :=খরচ[curr, dist - 1] + গ্রাফ[curr, i, 1]

      • q

        -এ ডেটা(প্রতিবেশী, ডিস্ট, খরচ[প্রতিবেশী, ডিস্ট]) সন্নিবেশ করান

• রিটার্ন -1

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int node, dist, cost;
   Data(int a, int b, int c){
      node = a;
      dist = b;
      cost = c;
   }
};
struct Comparator{
   bool operator() (Data a, Data b) {
      return !(a.cost < b.cost);
   }
};
class Solution {
public:
   vector<vector<int>> cost;
   int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
      cost = vector<vector<int> >(n + 1, vector<int>(K + 10, INT_MAX));
      vector<vector<int> > graph[n];
      for (int i = 0; i < flights.size(); i++) {
         int u = flights[i][0];
         int v = flights[i][1];
         graph[u].push_back({ v, flights[i][2] });
      }
      priority_queue<Data, vector<Data>, Comparator> q;
      q.push(Data(src, 0, 0));
      cost[src][0] = 0;
      int ans = -1;
      while (!q.empty()) {
         Data temp = q.top();
         int curr = temp.node;
         q.pop();
         int dist = temp.dist;
         if (curr == dst)
            return temp.cost;
         dist++;
         if (dist > K + 1)
            continue;
         for (int i = 0; i < graph[curr].size(); i++) {
            int neighbour = graph[curr][i][0];
            if (cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]) {
               cost[neighbour][dist] = cost[curr][dist - 1] + graph[curr][i][1];
               q.push(Data(neighbour, dist, cost[neighbour][dist]));
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,100},{1,2,100},{0,2,500}};
   cout << (ob.findCheapestPrice(3, v, 0, 2, 1));
}

ইনপুট

3, {{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1

আউটপুট

200