Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
高桥君是 Atcoder 王国的国王。Atcoder 王国包括N个城市(编号11~N)和m条双向的道路。每条道路都有长度。对于 Atcoder 王国中的任意城市 [A,B],都可以保证从A到B有多条道路。
高桥君认为,Atcoder人的幸福在很大程度上取决于交通的便利性。为了找出人们的幸福程度,他想找到所有可能城市之间最短路径长度的总和S。
如果城市i和j之间的最短路径的长度为 D(i,j),则
img
高桥先生正计划建造K条新道路作为公共项目。这样的建设可能会导致多于两条或两条直接连接城市的道路,在这种情况下,现有道路将不会被拆除,而是会被增加。
您的任务是按照给定的顺序建造一条新路,并编写一个程序来计算上述每种施工的S。
第一行两个数n和m,分别表示城市数和道路数。接下来2~m+1行每行三个数u,v,w表示有一条连接u,v城市的长度为w的路径。第m+2行一个数k,表示有k条新的路要修建。第m+3~m+k+2行每行三个数x,y,z,表示又要建一条连接x,y的长度为z的路径。
输出k行,每行一个数,表示在修完第ii条道路后的S。
输入 #1
4 3
1 2 1
2 3 1
3 4 10
2
3 4 1
1 4 1
输出 #1
10
8
输入 #2
8 16
8 7 38
2 8 142
5 2 722
8 6 779
4 6 820
1 3 316
1 7 417
8 3 41
1 4 801
3 2 126
4 2 71
8 4 738
4 3 336
7 5 717
5 6 316
2 1 501
10
6 1 950
6 1 493
1 6 308
3 4 298
2 5 518
1 5 402
4 7 625
7 6 124
3 8 166
2 4 708
输出 #2
13649
12878
11954
11954
11280
11058
11058
8099
8099
8099
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void best_coder() {
int n, m;
cin >> n >> m;
int INF = 1e9;
vector<vector<int>> g(n, vector<int>(n, INF));
for (int i = 0; i < m; ++i) {//存储边的情况
int u, v, w;
cin >> u >> v >> w;
--u;
--v;
g[u][v] = w;
g[v][u] = w;
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
g[i][i] = 0;
for (int j = 0; j < n; ++j) {
if (j == i) {
continue;
}
for (int s = 0; s < n; ++s) {
if (s == i || s == j) {
continue;
}
g[j][s] = min(g[j][s], g[i][s] + g[j][i]);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ans += g[i][j];
}
}
int k;
cin >> k;
for (int i = 0; i < k; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a;
--b;
if (c >= g[a][b]) {
cout << ans / 2 << endl;
continue;
}
ans -= 2 * (g[a][b] - c);
g[a][b] = c;
g[b][a] = c;
for (int j = 0; j < n; ++j) {
for (int s = 0; s < n; ++s) {
int t = g[j][s];
g[j][s] = min(g[b][s] + g[j][a] + g[a][b] , min(g[j][s], g[a][s] + g[j][b] + g[a][b]));
ans -= t - g[j][s];
}
}
cout << ans / 2 << endl;
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}