warshall_uva821.cpp

#include<bits/stdc++.h>

using namespace std ;

#define M 999999999
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n ) for(i = 0 ; i< n ;i++ )

typedef long long LL ;

void warshall(LL arr[][200] ,LL num){
    LL i , j , k ;
    for(k =1 ; k <= num ;k++){
        for(i = 1 ;i<= num ;i++ ){
            for(j =  1;j<= num ; j++)
            {
                if(arr[i][k] + arr[k][j] <= arr[i][j]){
                    arr[i][j] = arr[i][k] + arr[k][j] ;
                }

            }
    }
}

return ;
}

int main(){
   // freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);

LL tc , i ,j , k;
LL arr[200][200] , _time[200][200], p=0;

LL a , b ,count = 1;
int cs = 0;
map<int , int >m ;
while(scanf("%lld%lld",&a , &b )){
    if( a == 0 && b == 0 ) break ;
    m.clear();
    for(i = 1 ;i<= 100 ;i++ ){
        for(j =  1;j<= 100 ; j++){
            arr[i][j] = M;
        }
        }
    for(i = 1 ;i<= 100 ;i++ ){
            arr[i][i] = 0;
        }
    m[a] = count++;
    m[b] =  count++;

    arr[a][b] =  1;

    while(scanf("%lld%lld",&a , &b )){
    if( a == 0 && b == 0 ) break ;
        if(m.find(a) == m.end() )m[a] =  count++ ;
        if(m.find(b) == m.end() )m[b] =  count++ ;

        arr[m[a] ][m[b]] =  1 ;


    }

    count-- ;
    warshall(arr , count);
    LL sum = 0 ;
    double ret ;
    LL num = count;

    for(i = 1 ;i<= num ;i++ ){
        for(j =  1;j<= num ; j++){
            sum += arr[i][j];

        }
    }
    count =  count*count  - count;

    ret =(double) sum/count ;

    pf("Case %d: average length between pages = %.3lf clicks\n", ++cs , ret);
//    pf("%lld %lld\n",sum  , count );
count =  1;
}

    return 0;
}