题目链接：点我点我
题意：给出一个最短路的图，询问是否正确，如果正确的话，输出遍历所有点的最短路径和。
题解：判断是否正确的，直接再一次Floyd，判断是否会有A[i][k]+A[k][j]<A[i][j]（通过中间点k使得两点间距离更短），如果有的话，直接输出-1。
要遍历到所有道路，并且路径和最小，我们可以尽可能用用中间点的路径（A[i][k]+A[k][j]==A[i][j]），这样本来遍历两个点，就可以遍历3个点了，
最后加的时候记得不要从重复加，从最小点往后加，不要再往前加，不然就重复了。
（其实如果重复计算也不要紧，就相当于过去又回来，会是答案的两倍，除以2就行了）
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 ?5 const int N=333; 6 typedef long long LL; 7 int A[N][N],idx[N][N]; 8 ?9 int main(){10 ????int n,flag=1;11 ????LL ans=0;12 ????cin>>n;13 ????for(int i=1;i<=n;i++)14 ????for(int j=1;j<=n;j++)15 ????cin>>A[i][j],idx[i][j]=0;16 ????17 ????for(int k=1;k<=n;k++){18 ????????for(int i=1;i<=n;i++){19 ????????????for(int j=1;j<=n;j++){20 ????????????????if(i==j||i==k||j==k) continue;21 ????????????????if(A[i][k]+A[k][j]<A[i][j]) flag=0;22 ????????????????if(A[i][k]+A[k][j]==A[i][j]) idx[i][j]=1;23 ????????????}24 ????????}25 ????}26 ????27 ????if(!flag) {cout<<-1<<endl;return 0;}28 ????for(int i=1;i<=n;i++){29 ????????for(int j=i+1;j<=n;j++){//这边可以直接从1开始,这样的话相当于重复计算一次,最后ans/2就行了 30 ????????????if(!idx[i][j]) ans+=A[i][j];31 ????????}32 ????}33 ????34 ????cout<<ans<<endl;35 ????return 0;36 }AtCoder Beginner Contest 074 D - Restoring Road Network（Floyd变形）
原文地址：http://www.cnblogs.com/Leonard-/p/7554659.html