電車で出発地から目的地の駅に到達するために必要な最小時間を見つけるためのC++プログラム

n個のステーションがm個のトラックで接続されているとします。ステーションの名前は1からnです。トラックは双方向であり、ステーションsrcからステーションdestに到達する必要があります。 i番目の鉄道の出発地と目的地の駅は配列「roads」で指定されます。roads[i]の形式は{station1、station2}です。 j番目の駅から、列車は時間kjの倍数で駅に接続されているすべての駅に向けて出発し、各列車は目的地に到達するのにtjの時間を要します。値は配列'departure'で指定され、各要素の形式は{tj、kj}です。ここで、srcからdestに到達するのにかかる最小時間を把握する必要があります。複数の列車を乗り換えることができ、列車の乗り換えにかかる時間はごくわずかです。

したがって、入力がn =4、m =3、src =1、dst =4、roads ={{1、2}、{2、4}、{3、4}}、departure ={{2 、1}、{3、5}、{7、6}}の場合、出力は8になります。

駅1から、時間0で駅2まで電車に乗ります。駅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