মান লিজিয়ে, n টি স্টেশন m টি ট্র্যাক দ্বারা সংযুক্ত। স্টেশনগুলো ১ থেকে 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।
স্টেশন ১ থেকে সময় ০-তে ট্রেন নিয়ে স্টেশন ২-এ যাওয়া হয়। স্টেশন ২ পৌঁছাতে ২ একক সময় লাগে। স্টেশন ২ থেকে সময় ৫-তে ট্রেন নিয়ে স্টেশন ৪-এ যাওয়া হয়। স্টেশন ৪ পৌঁছাতে ৩ একক সময় লাগে। মোট সময় = (৫ + ৩) = ৮।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
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]-র ২য় মান graph[a]-র শেষে (b, t, k) যোগ করুন graph[b]-র শেষে (a, t, k) যোগ করুন dp অ্যারে সংজ্ঞায়িত করুন আকার n, মান -9999 priq প্রায়োরিটি কিউ সংজ্ঞায়িত করুন যা পেয়ার ধারণ করবে dp[src] := 0 priq-তে pair(-dp[src], src) যোগ করুন while priq খালি নয়: (w, a) := priq-র সর্বোচ্চ মান priq-র থেকে মুছুন if a == dst, তবে: return -w if w < dp[a], তবে: continue graph[a]-র প্রতিটি v জন্য: (b, t, k) := v weight := (w - k + 1) / k * k - t if weight > dp[b], তবে: dp[b] := weight priq-তে pair(weight, b) যোগ করুন 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
