题目大概意思：给定一个图，任意俩点间的最短路已知，判断该图是否存在，若不存在，则输出impossible，存在，输出可能的最少边数
分析：
首先，判断该图是否存在，这个很容易，对已给的图求出任意点的最短路，若存在俩点最短路与原图不同（即所给图存在更短路)，则不存在;
若该图存在，求出最少的边数，其实就是一个删边的过程，起始的边数是n*（n-1)，若俩点之间存在其他路径长等于直接相连时的路径长，则删去，注意，要判断是否重复删边（orz，这里WA了几次）；
求任意俩点之间的最短路，用floyd算法，复杂度O（n^3)，因为n最大为100，无压力~~
View Code #include<iostream>using namespace std;int map[101][101],g[101][101],n;bool mat[101][101];int main(){int cas,T=0; scanf("%d",&cas);while(cas--) { scanf("%d",&n);int count=n*(n-1);for(int i=0;i<n;i++)for(int j=0;j<n;j++) { scanf("%d",&map[i][j]); g[i][j]=map[i][j]; } memset(mat,0,sizeof(mat));for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++) { if(i==j)continue;if(map[i][k]&&map[k][j]&&g[i][j]>=g[i][k]+g[k][j]) {if(g[i][j]==g[i][k]+g[k][j]&&!mat[i][j]) { mat[i][j]=1;//记录是否删过 count--; } g[i][j]=g[i][k]+g[k][j]; } }int flag=0; printf("Case %d: ",++T);for(int i=0;i<n;i++) {for(int j=0;j<n;j++)if(g[i][j]&&g[i][j]!=map[i][j])//判断是否存在更短路 { flag=1;break; }if(flag)break; }if(!flag) printf("%d\n",count);else printf("impossible\n"); }return 0;}转载于:https://www.cnblogs.com/nanke/archive/2011/09/12/2173982.html
相关资源：数据结构—成绩单生成器