मान लीजिए n स्टेशन m पटरियों से जुड़े हैं। स्टेशन 1 से n तक नामित हैं। पटरियाँ द्विदिश हैं और हमें स्टेशन src से स्टेशन dst तक पहुँचना है। i-वें रेलमार्ग के स्रोत और गंतव्य स्टेशन 'roads' सरणी में दिए गए हैं जहाँ roads[i] का प्रारूप {station1, station2} है। j-वें स्टेशन से, समय kj के गुणकों पर सभी जुड़े स्टेशनों के लिए ट्रेन प्रस्थान करती है और प्रत्येक ट्रेन को गंतव्य तक पहुँचने में tj समय लगता है। ये मान 'departure' सरणी में दिए गए हैं जहाँ प्रत्येक तत्व {tj, kj} प्रारूप में है। हमें src से dst तक पहुँचने में लगने वाले न्यूनतम संभावित समय की गणना करनी है। हम कई ट्रेनें बदल सकते हैं और ट्रेन बदलने में लगने वाला समय नगण्य है।
उदाहरण के लिए, यदि इनपुट है 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 के लिए ट्रेन लेते हैं। स्टेशन 4 पहुँचने में 3 समय लगता है। कुल समय (5 + 3) = 8।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
src := src - 1
dst := dst - 1
टपल्स वाला एक नया सरणी graph[n] परिभाषित करें
i := 0 से m-1 तक:
a := roads[i] का पहला मान - 1
b := roads[i] का दूसरा मान - 1
t := departure[i] का पहला मान
k := departure[i] का दूसरा मान
टपल (b, t, k) को graph[a] के अंत में डालें
टपल (a, t, k) को graph[b] के अंत में डालें
आकार n का सरणी dp परिभाषित करें जिसे -9999 से आरंभ किया गया हो
युग्मों वाली एक प्राथमिकता कतार priq परिभाषित करें
dp[src] := 0
priq में युग्म (-dp[src], src) डालें
जब तक priq खाली न हो:
टपल (w, a) := priq का सबसे बड़ा मान
priq से शीर्ष तत्व हटाएँ
यदि a == dst, तो:
-w लौटाएँ
यदि w < dp[a], तो:
अगली पुनरावृत्ति पर जाएँ
graph[a] में प्रत्येक v के लिए:
टपल (b, t, k) बनाएँ
weight := (w - k + 1) / k * k - t
यदि weight > dp[b], तो:
dp[b] := weight
priq में युग्म (weight, b) डालें
-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