C++ 程序找出所有给定三元组的最短成本路径的总和
假设有 n 个城市，城市之间有 m 条道路。m 条道路以一系列道路的形式提供给我们，其中道路的格式为 {aource, destination, weight}。现在，我们定义一个三元组 (s, t, k)，其中 s、t 和 k 是城市。现在我们必须计算从城市 s 到城市 t 所需的最短时间。要从 s 访问 t，只能访问 1 到 k 范围内的城市。如果城市 t 不能从 s 到达，那么我们返回 0。我们必须计算所有三元组 (s, t, k) 的最短时间，并打印它们的总和。
因此，如果输入类似于 n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}，则输出将为 63。
脚步
为了解决这个问题，我们将遵循以下步骤 -
Define one 2D array dvec initialized with value infinityfor initialize i := 0, when i < n, update (increase i by 1), do:
dvec[i, i] := 0
for initialize i := 0, when i < m, 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
dvec[a, b] := c
res := 0
for initialize k := 0, when k < n, update (increase k by 1), do:
for initialize i := 0, when i < n, update (increase i by 1), do:
for initialize j := 0, when j < n, update (increase j by 1), do:
dvec[i, j] := minimum of (dvec[i, j] and dvec[i, k] + dvec[k, j])
if dvec[i, j] is not equal to infinity, then:
res := res + dvec[i, j]
print(res)
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>using namespace std;
const int INF = 1e9;
void solve(int n, int m, vector<tuple<int, int, int>> edges){
vector<vector<int>> dvec(n, vector<int>(n, INF));
for(int i = 0; i < n; i++)
dvec[i][i] = 0;
for(int i = 0; i < m; i++) {
int a = get<0> (edges[i]);
int b = get<1> (edges[i]);
int c = get<2> (edges[i]);
a--; b--;
dvec[a][b] = c;
}
int res = 0;
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]);
if(dvec[i][j] != INF)
res += dvec[i][j];
}
}
}
cout << res << endl;
}
int main() {
int n = 4, m = 2;
vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}};
solve(n, m, edges);
return 0;
}
输入
4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}输出结果63
以上是 C++ 程序找出所有给定三元组的最短成本路径的总和 的全部内容， 来源链接： utcz.com/z/297228.html
