मान लीजिए 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। प्रत्येक शहर से राउंड-ट्रिप करने में 26 समय लगता है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
युग्मों वाला एक 2D सरणी graph(n) परिभाषित करें
i := 0 से m-1 तक:
x := roads[i] का पहला मान
y := roads[i] का दूसरा मान
z := roads[i] का तीसरा मान
x और y को 1 घटाएँ
युग्म (y, z) को graph[x] के अंत में डालें
i := 0 से n-1 तक:
q := एक नई प्राथमिकता कतार
एक सरणी dst परिभाषित करें
युग्म (0, i) को q के शीर्ष पर डालें
जब तक q का आकार शून्येतर:
युग्म p := q का शीर्ष मान
q से शीर्ष तत्व हटाएँ
dt := p का पहला मान
curr := p का दूसरा मान
यदि dst[curr] == 0, तो:
dst[curr] := dt
लूप से बाहर निकलें
यदि dst[curr] != -1, तो:
जारी रखें
dst[curr] := dt
graph[curr] में प्रत्येक next तत्व के लिए:
tp := next का पहला मान
cst := next का दूसरा मान
युग्म (dt + cst, tp) को q के शीर्ष पर डालें
यदि dst[i] == 0, तो dst[i] := -1
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