[Arc083D/At3535]
有 \(N\) 个城市，城市与城市之间用长度为整数的无向道路连接。
现有一考古学家找到了一张 \(N×N\) 的表 \(A\) ，这张表代表了这 \(N\) 座城市两两之间的最短路。即表中的第 \(u\) 行第 \(v\)列的值代表了从城市 \(u\)到\(v\)的最短路长度。
问能否根据这张表，求出高桥王国的最小道路长度总和。
——————————
考虑到原图中的边一定就在这个最短路矩阵中，我们只需要保留其中的一些，让它们“表示”出其它就可以了
那么我们是否可以将最短路矩阵看成图，所有“冗余”边删掉，就得到了结果呢？
猜得这样得出的结果就是最优的
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 305;
int n,g[305][305],ans;
signed main() {
cin>>n;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
cin>>g[i][j];
ans+=g[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
if(i==j) continue;
if(j==k) continue;
if(k==i) continue;
if(g[i][j] > g[i][k]+g[k][j]) {
cout<<-1;
return 0;
}
if(g[i][j] == g[i][k]+g[k][j]) {
ans-=g[i][j];
break;
}
}
}
}
cout<<ans/2ll<<endl;
}