【算法】图论，最短路？
【题意】原图为无向连通图，现给定原图的最短路矩阵，求原图最小边权和，n<=300。
【题解】要求最小边权和下，原图的所有边一定是所连两端点的最短路。
那么现在将所有最短路作为边加入原图，考虑删边。
对于(u,v)，若存在点w使得(u,v)=(u,w)+(w,v)，则(u,v)可以删去。（btw，若是>则无解）
复杂度O(n^3)。
#include<cstdio>#include<cstring>#include<cctype>#include<cmath>#include<algorithm>#define ll long longusing namespace std;int read(){ ???char c;int s=0,t=1; ???while(!isdigit(c=getchar()))if(c==‘-‘)t=-1; ???do{s=s*10+c-‘0‘;}while(isdigit(c=getchar())); ???return s*t;}/*------------------------------------------------------------*/const int inf=0x3f3f3f3f,maxn=310; int n,map[maxn][maxn],f[maxn][maxn]; int abs(int x){return x>0?x:-x;}int main(){ ???n=read(); ???for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)map[i][j]=read(),f[i][j]=map[i][j]; ???bool ok=1; ???for(int i=1;i<n;i++){ ???????for(int j=i+1;j<=n;j++){ ???????????for(int k=1;k<=n;k++)if(i!=k&&j!=k){ ???????????????if(map[i][j]>map[i][k]+map[k][j])ok=0; ???????????????if(map[i][j]==map[i][k]+map[k][j])f[i][j]=f[j][i]=0; ???????????} ???????} ???} ???long long ans=0; ???for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans+=f[i][j]; ???if(ok)printf("%lld",ans/2);else printf("-1"); ???return 0;}【Atcoder】ARC083 D - Restoring Road Network
原文地址：http://www.cnblogs.com/onioncyc/p/7535216.html