सी++ प्रोग्राम ट्रेन द्वारा स्रोत से गंतव्य स्टेशन तक पहुंचने के लिए आवश्यक न्यूनतम समय का पता लगाने के लिए

मान लीजिए n स्टेशन m ट्रैक से जुड़े हुए हैं। स्टेशनों का नाम 1 से n तक रखा गया है। ट्रैक द्विदिश हैं, और हमें स्टेशन स्रोत से स्टेशन गंतव्य तक पहुंचना है। आई-वें रेलमार्ग के स्रोत और गंतव्य स्टेशन 'सड़कों' की श्रेणी में दिए गए हैं जहां सड़कें [i] {स्टेशन1, स्टेशन2} प्रारूप की हैं। j-th स्टेशन से, एक ट्रेन स्टेशन से जुड़े सभी स्टेशनों के लिए kj के गुणकों पर निकलती है और प्रत्येक ट्रेन को गंतव्य तक पहुंचने में tj समय लगता है। मान एक सरणी 'प्रस्थान' में दिए गए हैं जहाँ प्रत्येक तत्व {tj, kj} प्रारूप का है। अब, हमें स्रोत से गंतव्य तक पहुँचने में लगने वाले न्यूनतम संभव समय का पता लगाना होगा। हम कई ट्रेनों को बदल सकते हैं और ट्रेनों को बदलने में लगने वाला समय नगण्य है।

इसलिए, यदि इनपुट n =4, m =3, src =1, dst =4, सड़कें ={{1, 2}, {2, 4}, {3, 4}}, प्रस्थान ={{2 , 1}, {3, 5}, {7, 6}}, तो आउटपुट 8 होगा।

स्टेशन 1 से हम ट्रेन को समय 0 पर स्टेशन 2 तक ले जाते हैं। स्टेशन 2 तक पहुँचने में लगने वाला समय 2 है। स्टेशन 2 से हम ट्रेन को स्टेशन 4 पर 5 समय पर ले जाते हैं। स्टेशन 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}}