【SSL 1588】猜道路（图论）

猜道路

题目链接：SSL 1588

题目大意

给你 n 个点之间的最短路径，要你找到原来图上路径的总长度最短可以是多少，如果没有满足的图则输出 -1。

思路

首先至于判断满足这个很简单，因为只有图是满足是最短路的一定能构造。
所以你只需要判一下是否存在 $a_{i,j}>a_{i,k}+a-k,j$ 这样的不合法情况即可。

那考虑构造，会发现其实生成树并不对，因为你完全没必要走树上的，可以开一条捷径之类的。
所以我们考虑一个条边怎样才不需要。
那就是它可以被替代，也就是存在 $a_{i,k}+a_{k,j}=a_{i,j}$ 的时候，$a_{i,j}$ 就不被需要了。

那你把剩下需要的边的边权加起来，就是答案了。

代码

#include
#include
#define ll long long 

using namespace std;

const int N = 305;
int n, a[N][N], fa[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j && i != k && j != k) {
					if (a[i][j] > a[i][k] + a[k][j]) {
						printf("-1"); return 0;
					}
				}
	
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (i != j) {
				bool in = 1;
				for (int k = 1; k <= n; k++) if (k != i && k != j)
					if (a[i][j] == a[i][k] + a[k][j]) {
						in = 0; break;
					}
				if (in) ans += a[i][j];
			}
	printf("%lld", ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40