Chương trình C ++ để tìm ra khoảng thời gian tối thiểu cần thiết để đi từ nguồn đến ga đích bằng tàu hỏa

Giả sử n trạm được nối với nhau bởi m đường ray. Các trạm được đặt tên từ 1 đến n. Đường ray là hai chiều và chúng ta phải đến trạm đích từ trạm src. Các ga nguồn và ga đích của tuyến đường sắt thứ i được cho trong mảng 'đường' trong đó đường [i] có định dạng {ga1, ga2}. Từ ga thứ j, một đoàn tàu khởi hành đến tất cả các ga nối với ga đó theo bội số thời gian kj và mỗi chuyến tàu mất tj khoảng thời gian để đến đích. Các giá trị được đưa ra trong một mảng 'khởi hành' trong đó mỗi phần tử có định dạng {tj, kj}. Bây giờ, chúng ta phải tìm ra thời gian tối thiểu có thể cần để truy cập từ src đến đích. Chúng tôi có thể thay đổi nhiều chuyến tàu và thời gian thay đổi các chuyến tàu là không đáng kể.

Vì vậy, nếu đầu vào là n =4, m =3, src =1, dst =4, đường ={{1, 2}, {2, 4}, {3, 4}}, khởi hành ={{2 , 1}, {3, 5}, {7, 6}}, thì đầu ra sẽ là 8.

Từ ga 1 ta đi tàu đến ga 2 lúc 0. Thời gian đi tàu đến ga 2 là 2. Từ ga 2, ta đi tàu đến ga 4 lúc 5. Thời gian đi tàu đến ga 2 là 3. Vậy tổng thời gian thực hiện là (5 + 3) =8.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

8