मान लीजिए, 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