n개의 스테이션이 m개의 트랙으로 연결되어 있다고 가정합니다. 스테이션의 이름은 1에서 n까지입니다. 트랙은 양방향이며 src 역에서 목적지 역에 도달해야 합니다. i번째 철도의 출발지와 목적지 역은 'roads' 배열에 주어집니다. 여기서 road[i]는 {station1, station2} 형식입니다. j번째 역에서 기차는 시간 kj의 배수로 역과 연결된 모든 역으로 출발하며 각 기차는 목적지에 도달하는 데 tj의 시간이 걸립니다. 값은 각 요소가 {tj, kj} 형식인 'departure' 배열에 제공됩니다. 이제 src에서 dest까지 도달하는 데 걸리는 가능한 최소 시간을 알아내야 합니다. 우리는 여러 대의 열차를 변경할 수 있으며 열차를 변경하는 데 걸리는 시간은 무시할 수 있습니다.
따라서 입력이 n =4, m =3, src =1, dst =4, 도로 ={{1, 2}, {2, 4}, {3, 4}}, 출발 ={{2 , 1}, {3, 5}, {7, 6}}, 출력은 8이 됩니다.
역 1에서 역 2까지 시간 0에 기차를 타십시오. 역 2에 도달하는 데 걸리는 시간은 2입니다. 역 2에서 역 4까지 시간 5에 기차를 타십시오. 역 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