Chương trình C ++ để tìm ra đường dẫn chi phí ngắn nhất trong một biểu đồ nhất định cho q truy vấn

Giả sử, chúng ta được cho một đồ thị chứa n đỉnh và liên thông cực tiểu. Các cạnh được cung cấp cho chúng ta một mảng trong đó các cạnh được cho ở định dạng {nguồn, đích, trọng số}. Bây giờ, chúng ta nhận được q số truy vấn trong đó mỗi truy vấn có định dạng {nguồn, đích}. Chúng ta phải tìm đường đi ngắn nhất từ ​​nguồn đến đích qua đỉnh k. Chúng tôi in chi phí của đường dẫn cho mỗi truy vấn.

Vì vậy, nếu đầu vào là n =6, q =3, k =1, các cạnh ={{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5 , 3}, {5, 6, 2}}, queries ={{1, 4}, {2, 6}, {2, 5}}, thì đầu ra sẽ là 6 11 9.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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])

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, {{1, 4}, {2, 6}, {2, 5}}

Đầu ra

6
11
9