[ABC208D] Shortest Path Queries 2 题解

思路解析

此题的本质其实就是 Floyd。我们在进行 Floyd 时会有一个 \(k\) 充当中间点，可见这里的 \(k\) 就等于题目当中的 \(k\)，因为小于等于 \(k\) 的所有点都被当作过中间点转移过，而大于 \(k\) 的所有点都没有被当作过中间点转移过，于是直接进行 Floyd 即可。

一定要记得特判 Floyd 中 \(i=j\) 的情况。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 410;
int n, m, f[N][N];
signed main() {
	memset(f, 0x3f, sizeof(f));
	cin >> n >> m;
	for(int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		f[u][v] = w;
	}
	int ans = 0;
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i != j) {
					f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
					if(f[i][j] < 1e16) ans += f[i][j];
				}
			}
		}
	}
	cout << ans;
	return 0;
}