ধরুন, n শহর আছে এবং m রাস্তাগুলি তাদের সংযুক্ত করছে। প্রতিটি রাস্তা একমুখী, এবং উৎস শহর থেকে গন্তব্য শহরে পৌঁছতে এটি একটি নির্দিষ্ট পরিমাণ সময় নেয়। রাস্তার তথ্য অ্যারে রাস্তাগুলিতে দেওয়া হয় যেখানে প্রতিটি উপাদান বিন্যাসের (উৎস, গন্তব্য, সময়)। এখন, একজন ব্যক্তি এক শহর থেকে অন্য শহরে ভ্রমণ করছেন এবং ট্রিপটি একটি রাউন্ড ট্রিপ হতে হবে। একটি ট্রিপকে রাউন্ড-ট্রিপ বলা যেতে পারে যখন ব্যক্তি একটি নির্দিষ্ট শহর থেকে শুরু করে, এক বা একাধিক রাস্তা দিয়ে যায় এবং একই শহরে ট্রিপ শেষ করে। তাই প্রতিটি শহরের জন্য, সেই নির্দিষ্ট শহর থেকে রাউন্ড-ট্রিপ সম্ভব কিনা তা নির্ধারণ করতে হবে। যদি সম্ভব হয়, রাউন্ড-ট্রিপ করার জন্য প্রয়োজনীয় সময়টি প্রিন্ট করুন বা অন্যথায় প্রিন্ট করুন -1।
সুতরাং, যদি ইনপুট হয় n =4, m =4, রাস্তা ={{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}} , তাহলে আউটপুট হবে:26 26 26 26। প্রতিটি শহর থেকে, একটি রাউন্ড-ট্রিপ করতে সময় লাগে 26।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one 2D array graph(n) of pairs
for initialize i := 0, when i < m, update (increase i by 1), do:
x := first value of roads[i]
y := second value of roads[i]
z := third value of roads[i]
decrease x and y by 1
insert pair (y, z) at the end of graph[x]
for initialize i := 0, when i < n, update (increase i by 1), do:
q := a new priority queue
Define an array dst
insert pair (0, i) at the top of q
while size of q is non-zero, do:
pair p := top value of q
delete the top element from q
dt := first value of p
curr := second value of p
if dst[curr] is same as 0, then:
dst[curr] := dt
Come out from the loop
if dst[curr] is not equal to -1, then:
Ignore following part, skip to the next iteration
dst[curr] := dt
for element next in graph[curr], do:
tp := first value of next
cst := second value of next
insert pair(dt + cst, tp) at the top of q
if dst[i] is same as 0, then:
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
