資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：求所有給定三元組的最短成本路徑之和
假設有n個城市和m條連線這些城市的道路。這m條道路在一個名為roads的陣列中給出，格式為{起點城市，終點城市，權重}。現在定義一個三元組(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 infinity for 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
更新於：2022年3月2日
瀏覽量：254
廣告