PersonalCorpus 版 (精华区)

// Your C++ program has solved Ok the problem 821 (Page Hopping)
// in 2.174 seconds using as much as 440 kbytes of virtual memory.
/*  @JUDGE_ID:  18188JK  821  C++  "Testing ..."  */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>
#include <ctype.h>

void Floyd(int dl[100][100], int n)
{
    int i,j,k;
    for (k=0;k<n;k++)
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
                if (dl[i][k]+dl[k][j]<dl[i][j])
                    dl[i][j]=dl[i][k]+dl[k][j];
}

void main()
{
#ifndef ONLINE_JUDGE
    freopen("D:\\acm\\i821.txt","r",stdin);
    freopen("D:\\acm\\o821.txt","w",stdout);
#endif

    int dl[100][100];
    int i,j,a,b,tot=0;

    while (1) {
        scanf("%d%d",&a,&b);
        if (a==0 && b==0) break;
        memset(dl,20,sizeof(dl));
        do {
            dl[a-1][b-1]=1;
            scanf("%d%d",&a,&b);
        } while (a!=0);
        Floyd(dl,100);
        a=0; b=0;
        for (i=0;i<100;i++)
            for (j=0;j<100;j++) if (dl[i][j]<10000 && i!=j) { 
                a+=dl[i][j];
                b++;
            }
        printf("Case %d: average length between pages = %.3lf clicks\n",++tot,(double)a/(double)b);
    }
}