Floyd Warshall.cpp

/* Floyd Warshall */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

#define MAX 105
int dist[MAX][MAX];
void floyd_warshall()
{
    for(int k=1; k<MAX; k++){
        for(int i=1; i<MAX; i++){
            for(int j=1; j<MAX; j++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    cout << i << " " << j << " " << dist[i][j] << endl;
                }
            }
        }
    }

    //Transitive Closure
    for(int k=1; k<MAX; k++){
        for(int i=1; i<MAX; i++){
            for(int j=1; j<MAX; j++){
                dist[i][j] == dist[i][j] || (dist[i][k] && dist[k][j]);
            }
        }
    }
}

int main()
{
    freopen("in.txt", "r", stdin);
    int u, v;
    int caseno = 0;
    while(scanf("%d %d", &u, &v)){
        if(u == 0 && v == 0) break;
        for(int i=1; i<MAX; i++){
            for(int j=1; j<MAX; j++){
                if(i == j) dist[i][j] = 0;
                else dist[i][j] = 1e9;
            }
        }
        int cnt = 0;
        while(scanf("%d %d", &u, &v)){
            if(u == 0 && v == 0) break;
            dist[u][v] = 1;
            cnt++;
        }
        floyd_warshall();
        int tot = 0;
        for(int i=1; i<MAX; i++){
            for(int j=1; j<MAX; j++){
                //if(dist[i][j] != 1e9 && dist[i][j] != 0) cout << dist[i][j] << " ";
            }
        }
        printf("Case %d: average length between pages = %0.3lf\n",++caseno, (double) tot/(cnt * 1.0));
    }
}