(UVA) 821 - Page Hopping [all-pair shortest path]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=762

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;

const int MAX_N = 101;
const int INF = 1e9+7;

int dp[MAX_N][MAX_N];

int main () {
    int i,j,c=1;
    while (scanf("%d %d",&i,&j) != EOF) {
        if (!i && !j) break;
        for (int i=1;MAX_N>i;i++) {
            for (int j=1;MAX_N>j;j++) {
                dp[i][j] = INF;
            }
        }
        dp[i][j]=1;
        while (scanf("%d %d",&i,&j)) {
            if (!i&&!j) break;
            dp[i][j]=1;
        }
        for (int k=1;MAX_N>k;k++) {
            for (int i=1;MAX_N>i;i++) {
                for (int j=1;MAX_N>j;j++) {
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        int sum=0;
        int cnt=0;
        for (int i=1;MAX_N>i;i++) {
            for (int j=1;MAX_N>j;j++) {
                if (dp[i][j] != INF && i!=j) {
                    sum += dp[i][j];
                    cnt++;
                }
            }
        }
        printf("Case %d: average length between pages = %.3f clicks\n",c++,double(sum)/cnt);
    }
}