মান লিজিয়ে, n টি শহর এবং m টি সড়ক আছে যা সেগুলোকে সংযুক্ত করে। প্রতিটি সড়ক একমুখী এবং স্রোত শহর থেকে গন্তব্য শহর পৌঁছাতে একটি নির্দিষ্ট সময় লাগে। সড়কদের তথ্য 'roads' অ্যারেতে দেওয়া আছে যেখানে প্রতিটি উপাদান হলো (স্রোত, গন্তব্য, সময়)। এখন একজন ব্যক্তি একটি শহর থেকে অন্য শহরে যাচ্ছে এবং যাত্রাটি হতে হবে রাউন্ড-ট্রিপ। একটি যাত্রাকে রাউন্ড-ট্রিপ বলা হয় যখন ব্যক্তিটি একটি নির্দিষ্ট শহর থেকে শুরু করে, এক বা একাধিক সড়ক দিয়ে যেতে থাকে, এবং একই শহরে ফিরে আসে। তাই প্রতিটি শহরের জন্য আমাদের নির্ধারণ করতে হবে যে কি সেখান থেকে রাউন্ড-ট্রিপ সম্ভব। যদি সম্ভব হয়, তবে রাউন্ড-ট্রিপের জন্য প্রয়োজনীয় সময় প্রিন্ট করব, অন্যথায় -1 প্রিন্ট করব।
যেমন, ইনপুট হলে n = 4, m = 4, roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}, তবে আউটপুট হবে: 26 26 26 26। প্রতিটি শহর থেকে রাউন্ড-ট্রিপ করতে ২৬ একক সময় লাগে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
graph(n) ২D অ্যারে সংজ্ঞায়িত করুন পেয়ার ধারণকারী i := 0 থেকে m-1 পর্যন্ত: x := roads[i]-র ১ম মান y := roads[i]-র ২য় মান z := roads[i]-র ৩য় মান x এবং y ১ কমিয়ে graph[x]-র শেষে pair(y, z) যোগ করুন i := 0 থেকে n-1 পর্যন্ত: q := নতুন প্রায়োরিটি কিউ dst অ্যারে সংজ্ঞায়িত করুন q-র শীর্ষে pair(0, i) যোগ করুন while q-র আকার নন-জিরো: p := q-র শীর্ষ মান q-র শীর্ষ উপাদান মুছুন dt := p-র ১ম মান curr := p-র ২য় মান if dst[curr] == 0, তবে: dst[curr] := dt লুপ থেকে বের হয়ে যান if dst[curr] != -1, তবে: continue dst[curr] := dt graph[curr]-র প্রতিটি next উপাদানের জন্য: tp := next-র ১ম মান cst := next-র ২য় মান q-র শীর্ষে pair(dt + cst, tp) যোগ করুন if dst[i] == 0, তবে: dst[i] := -1 print(dst[i])
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int modval = (int) 1e9 + 7; #define N 100 void solve(int n, int m, vector<tuple<int, int, int>> roads ) { vector<vector<pair<int, int>>> graph(n); for(int i = 0; i < m; i++) { int x, y, z; tie(x, y, z) = roads[i]; x--; y--; graph[x].emplace_back(y, z); } for(int i = 0; i < n; i++) { priority_queue<pair<int, int>> q; vector<int> dst(n, -1); q.emplace(0, i); while(q.size()){ pair<int, int> p = q.top(); q.pop(); int curr, dt; tie(dt, curr) = p; if(dst[curr] == 0) { dst[curr] = dt; break; } if(dst[curr] != -1) continue; dst[curr] = dt; for(auto next : graph[curr]){ int tp, cst; tie(tp, cst) = next; q.emplace(dt + cst, tp); } } if(dst[i] == 0) dst[i] = -1; cout<< dst[i]<< endl; } } int main() { int n = 4, m = 4; vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}; solve(n, m, roads); return 0; } ইনপুট
4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}} আউটপুট
26 26 26 26
