मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं और न्यूनतम रूप से जुड़ा हुआ है। किनारों को हमें एक सरणी दी जाती है जहां किनारों को {source, dest, weight} प्रारूप में दिया जाता है। अब, हमें प्रश्नों की q संख्या दी गई है जहां प्रत्येक क्वेरी {source, डेस्टिनेशन} प्रारूप की है। हमें स्रोत से गंतव्य तक शीर्ष k के माध्यम से सबसे छोटा लागत पथ खोजना होगा। हम प्रत्येक प्रश्न के लिए पथ की लागत प्रिंट करते हैं।
इसलिए, यदि इनपुट n =6, q =3, k =1, किनारों ={{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5 जैसा है। , 3}, {5, 6, 2}}, क्वेरीज़ ={{1, 4}, {2, 6}, {2, 5}}, तो आउटपुट 6 11 9 होगा।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
Define one 2D array graph of pairs of size n * n Define an array pathTotal of size n Define a function dfs(), this will take a, b, for each value i at graph[a]: if first value of i is same as b, then: Ignore following part, skip to the next iteration pathTotal[first value of i] := pathTotal[a] + second value of i dfs(first value of i, a) for initialize i := 0, when i < n - 1, update (increase i by 1), do: a := first value of (edges[i]) b := second value of (edges[i]) c := third value of (edges[i]) decrease a and b by 1 insert pair (b, c) at the end of graph[a] insert pair (a, c) at the end of graph[b] (decrease k by 1) dfs(k, k) for initialize i := 0, when i < q, update (increase i by 1), do: x := first value of queries[i] y := second value of queries[i] decrease x and y by 1 print(pathTotal[x] + pathTotal[y])
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> graph;
vector<int> pathTotal;
int k;
void dfs(int a, int b){
for(auto i : graph.at(a)){
if(i.first == b) continue;
pathTotal.at(i.first) = pathTotal.at(a) + i.second;
dfs(i.first,a);
}
}
void solve(int n, int q, vector<tuple<int, int, int>> edges,
vector<pair<int, int>> queries){
int a, b, c, x, y;
graph.resize(n);
pathTotal.resize(n);
for(int i = 0; i < n - 1; i++){
a = get<0> (edges[i]);
b = get<1> (edges[i]);
c = get<2> (edges[i]);
a--, b--;
graph.at(a).push_back(make_pair(b, c));
graph.at(b).push_back(make_pair(a, c));
}
k--;
dfs(k, k);
for(int i = 0; i < q; i++){
x = queries[i].first;
y = queries[i].second;
x--, y--;
cout << pathTotal.at(x) + pathTotal.at(y) << endl;
}
}
int main() {
int n = 6, q = 3;
k = 1;
vector<tuple<int, int, int>> edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}};
vector<pair<int, int>> queries = {{1, 4}, {2, 6}, {2, 5}};
solve(n, q, edges, queries);
return 0;
} इनपुट
6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, {{1, 4}, {2, 6}, {2, 5}}
आउटपुट
6 11 9