qクエリの特定のグラフで最短のコストパスを見つけるためのC++プログラム

n個の頂点を含み、最小限に接続されたグラフが与えられたとします。エッジは、エッジが{source、dest、weight}形式で指定されている配列に指定されます。これで、q個のクエリが与えられます。各クエリの形式は{source、destination}です。頂点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}}の場合、出力は6119になります。

ステップ

これを解決するには、次の手順に従います-

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