ট্রেনে উৎস থেকে গন্তব্য স্টেশনে পৌঁছানোর জন্য ন্যূনতম কত সময় প্রয়োজন তা খুঁজে বের করতে C++ প্রোগ্রাম

ধরুন n স্টেশনগুলি m ট্র্যাক দ্বারা সংযুক্ত। স্টেশনগুলির নামকরণ করা হয়েছে 1 থেকে n পর্যন্ত। ট্র্যাকগুলি দ্বিমুখী, এবং আমাদের স্টেশন src থেকে স্টেশনের গন্তব্যে পৌঁছাতে হবে। i-th রেলপথের উত্স এবং গন্তব্য স্টেশনগুলি অ্যারে 'রাস্তা'তে দেওয়া হয়েছে যেখানে রাস্তাগুলি[i] ফর্ম্যাট {station1, station2}। J-th স্টেশন থেকে, একটি ট্রেন স্টেশনের সাথে সংযুক্ত সমস্ত স্টেশনের জন্য kj সময়ের গুণে ছেড়ে যায় এবং প্রতিটি ট্রেন গন্তব্যে পৌঁছাতে tj পরিমাণ সময় নেয়। মানগুলি একটি অ্যারে 'প্রস্থান'-এ দেওয়া হয়েছে যেখানে প্রতিটি উপাদান বিন্যাস {tj, kj}। এখন, আমাদের src থেকে গন্তব্যে পৌঁছাতে ন্যূনতম সম্ভাব্য সময় বের করতে হবে। আমরা একাধিক ট্রেন পরিবর্তন করতে পারি এবং ট্রেন পরিবর্তন করতে যে সময় লাগে তা নগণ্য৷

সুতরাং, যদি ইনপুট হয় n =4, m =3, src =1, dst =4, রাস্তা ={{1, 2}, {2, 4}, {3, 4}}, প্রস্থান ={{2 , 1}, {3, 5}, {7, 6}}, তাহলে আউটপুট হবে 8।

স্টেশন 1 থেকে, আমরা ট্রেনটি স্টেশন 2 এ 0 সময়ে নিয়ে যাই। স্টেশন 2 তে পৌঁছতে সময় লাগে 2। স্টেশন 2 থেকে, আমরা 5 এ স্টেশন 4 এ ট্রেন ধরি। স্টেশন 2 এ পৌঁছতে সময় লাগে 3। সুতরাং মোট নেওয়া সময় হল (5 + 3) =8।

পদক্ষেপ

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

src := src - 1
dst := dst - 1
Define a new array graph[n] that contains tuples
for initialize i := 0, when i < m, update (increase i by 1), do:
   a := first value of roads[i] - 1
   b := second value of roads[i] - 1
   t := first value of departure[i]
   k := second value of departure[i]
   add tuple (b, t, k) at the end of graph[a]
   add tuple (a, t, k) at the end of graph[b]
Define an array dp of size n initialized with value -9999
Define a priority queue priq that contains pairs
dp[src] := 0
insert pair(-dp[src], src) at the end of priq
while not priq is empty, do:
   tuple containing (w, a) := largest value of priq
   delete top element from priq
   if a is same as dst, then:
      return -w
   if w < dp[a], then:
       Ignore following part, skip to the next iteration
   for each v in graph[a], do:
      create a tuple containing (b, t, k)
      weight := (w - k + 1) / k * k - t
      if weight > dp[b], then:
         dp[b] := weight
         insert pair(weight, b) at the end of priq
return -1

উদাহরণ

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

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

int solve(int n, int m, int src, int dst, vector<pair<int, int>> roads, vector<pair<int, int>> departure){
   src -= 1; 
   dst -= 1;
   vector<tuple<int, int, int>> graph[n];
   int a, b;
   int t, k;
   for(int i = 0; i < m; i++){
      a = roads[i].first - 1;
      b = roads[i].second - 1;
      t = departure[i].first;
      k = departure[i].second;
      graph[a].emplace_back(b, t, k);
      graph[b].emplace_back(a, t, k);
   }
   vector<int> dp(n, -9999);
   priority_queue<pair<int, int>> priq; 
   dp[src] = 0;
   priq.push(make_pair(-dp[src], src));
   int w;
   while(not priq.empty()){
      tie(w, a) = priq.top();
      priq.pop(); if(a == dst){
         return -w;
      }
      if(w < dp[a]) 
         continue;
      for(auto &v: graph[a]){
         tie(b, t, k) = v;
         int weight = (w - k + 1) / k * k - t; 
         if(weight > dp[b]){
            dp[b] = weight;
            priq.push(make_pair(weight, b));
         }
      }
   }
   return -1;
}
int main() {
   int n = 4, m = 3, src = 1, dst = 4;
   vector<pair<int, int>>
   roads = {{1, 2}, {2, 4}, {3, 4}},
   departure = {{2, 1}, {3, 5}, {7, 6}};
   cout<< solve(n, m, src, dst, roads, departure);
   return 0;
}

ইনপুট

4, 3, 1, 4, {{1, 2}, {2, 4}, {3, 4}}, {{2, 1}, {3, 5}, {7, 6}}

আউটপুট

8