821 - Page Hopping solution.

Problem Link: here

Problem Solution: All pair shortest path problem.

code:

#include<bits/stdc++.h>
using namespace std;
int node;
int dis[105][105];
map<int,int> mp;
map<int,int>:: iterator it;
int t=1;
void floyd()
{
    int i,j,k;
    for (k=1; k<=node; k++)
    {
        for (i=1; i<=node; i++)
        {
            for (j=1; j<=node; j++)
            {
                if (dis[i][j] > dis[i][k]+dis[k][j])
                {
                    dis[i][j] = dis[i][k]+dis[k][j];
                }

            }
        }
    }

}


int main()
{
    int cas=1;
    while(true)
    {
        int u,v;
        t=1;
        mp.clear();
        scanf("%d%d",&u,&v);
        int mx=0;
        if (u==0 && v==0) break;
        int i,j;

        for (i=0; i<=104; i++)
        {
            for (j=0; j<=104; j++)
            {
                if (i==j) dis[i][j]=0;
                else
                    dis[i][j] = 1000000;
            }

        }

        while(true)
        {

            if (mp.find(u) == mp.end()) mp[u]=t++;
            if (mp.find(v) == mp.end()) mp[v]=t++;
            dis[mp[u]][mp[v]]=1;
            scanf("%d %d", &u, &v);
            if (u == 0 && v == 0)
                break;
        }
        node=t-1;
        floyd();
        double total=0;
        for (i=1;i<=node;i++)
        {
            for (j=1;j<=node;j++)
            {
                if (i!=j) total+= dis[i][j];
            }
        }
        double vag = node*(node-1);
        printf("Case %d: average length between pages = %.3lf clicks\n",cas++,total/vag);
    }
    return 0;
}