有 \(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; }

[Arc083D/At3535] Restoring Road Network - 最短路,结论