C++ program to find out the minimum amount of time needed to reach from source to destination station by train

Suppose n stations are connected by m tracks. The stations are named from 1 to n. The tracks are bidirectional, and we have to reach station dest from station src. Thes source and destination stations of the i-th railroad is given in the array 'roads' where roads[i] is of the format {station1, station2}. From the j-th station, a train leaves for all stations that are connected with the station at the multiples of time kj and each train takes tj amount of time to reach the destination. The values are given in an array 'departure' where each element is of the format {tj, kj}. Now, we have to figure out the minimum possible time it takes to reach from src to dest. We can change multiple trains and the time taken to change the trains is negligible.

So, if the input is like n = 4, m = 3, src = 1, dst = 4, roads = {{1, 2}, {2, 4}, {3, 4}}, departure = {{2, 1}, {3, 5}, {7, 6}}, then the output will be 8.

From station 1, we take the train to station 2 at time 0. Time taken to reach station 2 is 2. From station 2, we take the train to station 4 at time 5. Time taken to reach station 2 is 3. So total time taken is (5 + 3) = 8.

Steps

To solve this, we will follow these steps −

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

Example

Let us see the following implementation to get better understanding −

#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; }

Input

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

Output

8