資料結構
網路
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 次檢視
廣告