uva 821 Page Hopping最短路floyd

题意：有n个结点，给定c条边的无权图，求任意两点的平均距离，如样例中：1到2，3，4的距离分别为1，1，2；2到1，3，4分别为3，2，1；3到1，2，4分别为1，2，3； 4到1，2，3分别为2，3，1； 思路：跑一遍Floyd求得任意两点的最短距离，根据要求求出平均最短距离即可 #include<cstdio> #include<cstring> using namespace std; const int maxn = 110; const int INF = 1<<20; int d[maxn][maxn],n; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; } int main() { int u,v,cas=0; while(scanf("%d%d",&u,&v)&&(u+v)) { n=-1; int Max = u>v?u:v; if(n<Max)n=Max; for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) d[i][j]=INF; d[u][v]=1; while(scanf("%d%d",&u,&v)&&(u+v)) { d[u][v]=1; int Max = u>v?u:v; if(n<Max)n=Max; } long long cnt; double ans; ans=cnt=0; floyd(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]!=INF) { ans+=d[i][j]; cnt++; } printf("Case %d: average length between pages = %.3lf clicks\n",++cas,(double)ans/cnt); } }