UVa 821 Page Hopping【Floyd】
题意：给出一个n个点的有向图，任意两个点之间都相互到达，求任意两点间最短距离的平均值
因为n很小，所以可以用floyd 建立出图，然后用floyd,统计d[][]不为0且不为INF的边的和及条数，就可以了
做的时候统计边的时候没有加不为0这个条件，改了好久= =
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=1005; 17 int d[maxn][maxn]; 18 19 int main(){ 20 int n,m,u,v,ans,kase=0; 21 while(scanf("%d %d",&u,&v)!=EOF){ 22 memset(d,0,sizeof(d)); 23 if(u==0&&v==0) break; 24 25 for(int i=1;i<=105;i++){ 26 for(int j=1;j<=105;j++){ 27 if(i==j) d[i][j]=0; 28 else d[i][j]=INF; 29 } 30 } 31 n=max(u,v);d[u][v]=1; 32 while(scanf("%d %d",&u,&v)!=EOF){ 33 if(u==0&&v==0) break; 34 n=max(max(u,v),n); 35 d[u][v]=1; 36 } 37 38 for(int k=1;k<=n;k++) 39 for(int i=1;i<=n;i++) 40 for(int j=1;j<=n;j++) 41 if(d[i][k]<INF&&d[k][j]<INF) 42 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 43 44 int sum=0,cnt=0; 45 46 for(int i=1;i<=n;i++) 47 for(int j=1;j<=n;j++) 48 if(d[i][j]!=INF&&d[i][j]!=0) sum+=d[i][j],cnt++; 49 50 double tmp=1.0*sum/cnt; 51 printf("Case %d: average length between pages = %.3lf clicks ",++kase,tmp); 52 } 53 return 0; 54 }