猜道路

题目链接：SSL 1588

题目大意

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

思路

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

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