q প্রশ্নের জন্য একটি প্রদত্ত গ্রাফে সংক্ষিপ্ততম খরচের পথ খুঁজে বের করতে C++ প্রোগ্রাম

ধরুন, আমাদের একটি গ্রাফ দেওয়া হয়েছে যাতে n শীর্ষবিন্দু রয়েছে এবং এটি ন্যূনতমভাবে সংযুক্ত। প্রান্তগুলি আমাদের একটি অ্যারে দেওয়া হয় যেখানে প্রান্তগুলি একটি {উৎস, গন্তব্য, ওজন} বিন্যাসে দেওয়া হয়। এখন, আমাদেরকে প্রশ্নগুলির q নম্বর দেওয়া হয়েছে যেখানে প্রতিটি প্রশ্ন বিন্যাস {উৎস, গন্তব্য}। আমাদের উৎস থেকে vertex k এর মাধ্যমে গন্তব্যে যাওয়ার সবচেয়ে কম খরচের পথটি খুঁজে বের করতে হবে। আমরা প্রতিটি প্রশ্নের জন্য পথের খরচ প্রিন্ট করি।

সুতরাং, যদি ইনপুট হয় n =6, q =3, k =1, প্রান্ত ={{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।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

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