मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं और यह न्यूनतम रूप से जुड़ा हुआ है। किनारे हमें एक ऐरे में दिए गए हैं जहां किनारे {स्रोत, गंतव्य, वजन} प्रारूप में दिए गए हैं। अब, हमें q संख्या के क्वेरी दिए गए हैं जहां प्रत्येक क्वेरी {स्रोत, गंतव्य} प्रारूप में है। हमें शीर्ष k के माध्यम से स्रोत से गंतव्य तक सबसे छोटे लागत पथ को ढूंढना है। हम प्रत्येक क्वेरी के लिए पथ की लागत प्रिंट करते हैं।
उदाहरण के लिए, यदि इनपुट n = 6, q = 3, k = 1, edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, queries = {{1, 4}, {2, 6}, {2, 5}} है, तो आउटपुट 6 11 9 होगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
आकार n * n के युग्मों का एक 2D ऐरे graph परिभाषित करें आकार n का एक ऐरे pathTotal परिभाषित करें एक फ़ंक्शन dfs() परिभाषित करें, जो a, b लेता है, graph[a] के प्रत्येक मान i के लिए: यदि i का पहला मान, b के बराबर है, तो: अगले पुनरावृत्ति पर जाएं pathTotal[i का पहला मान] := pathTotal[a] + i का दूसरा मान dfs(i का पहला मान, a) i := 0 से n - 2 तक, करें: a := edges[i] का पहला मान b := edges[i] का दूसरा मान c := edges[i] का तीसरा मान a और b को 1 से घटाएं युग्म (b, c) को graph[a] के अंत में डालें युग्म (a, c) को graph[b] के अंत में डालें k को 1 से घटाएं dfs(k, k) i := 0 से q-1 तक, करें: x := queries[i] का पहला मान y := queries[i] का दूसरा मान x और y को 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