q 쿼리에 대해 주어진 그래프에서 최단 비용 경로를 찾는 C++ 프로그램

n개의 꼭짓점을 포함하고 최소한으로 연결된 그래프가 있다고 가정합니다. 가장자리는 {source, dest, weight} 형식으로 가장자리가 제공되는 배열로 제공됩니다. 이제 각 쿼리가 {source, destination} 형식인 쿼리의 q개가 제공됩니다. 정점 k를 통해 소스에서 목적지까지의 최단 비용 경로를 찾아야 합니다. 각 쿼리에 대한 경로 비용을 인쇄합니다.

따라서 입력이 n =6, q =3, k =1, edge ={{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