有一张无向带权连通图(点数<=300),给出任意两点i,j之间的最短路长度dis[i][j].问是否存在一张这样的无向图.如果不存在输出-1.如果存在输出所有这样的无向图中边权和最小的一张的边权和.
如果存在i,j,k(i,j,k互不相同)使得dis[i][k]+dis[k][j]<dis[i][j]那么一定不存在.否则一定存在. 对于i,j(i!=j),如果存在第三个点k使得dis[i][k]+dis[k][j]=dis[i][j],那么为了总的边权和最小,i和j必然没有连边,i和j之间的最短路径是从i到k的最短路径和k到j的最短路径连接起来得到的. 如果不存在这样的k,i和j之间必然存在一条边权为dis[i][j]的边. O(n^3)完事了.
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=305; int dis[maxn][maxn]; bool notneed[maxn][maxn]; int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ scanf("%d",&dis[i][j]); } } bool flag=true; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ for(int k=1;k<=n;++k){ if(i!=j&&j!=k&&k!=i){ if(dis[i][j]+dis[j][k]<dis[i][k])flag=false; if(dis[i][j]+dis[j][k]==dis[i][k])notneed[i][k]=true; } } } } if(!flag){ printf("-1\n"); }else{ long long ans=0; for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(!notneed[i][j])ans+=dis[i][j]; } } printf("%lld\n",ans); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7533135.html
相关资源：数据结构—成绩单生成器