数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：查找给定图中q个查询的最短成本路径
假设我们得到一个包含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。
步骤
为了解决这个问题，我们将遵循以下步骤：
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
更新于：2022年3月2日
475 次浏览
广告