数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2022年3月2日
372 次查看
广告