假设 n 个站点由 m 个轨道连接。这些站的名称从 1 到 n。轨道是双向的，我们必须从 station src 到达 station dest。第 i 条铁路的源站和目的地站在数组“roads”中给出，其中 road[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}}，department = {{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
