Solution of UVa 821 Page Hopping

/* Bismillahir Rahmanir Rahim Solution-Using "Floyd Warshall" */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define ll long long using namespace std; set<ll>st; ll dis[101][101]; int main(){ ll n, e, u, v, w, cs=1, mx, sum, sz; float ans; while(1){ mx=0, sum=0; for(ll i=1; i<=100; i++){ for(ll j=1; j<=100; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; while(1){ cin>>u>>v; if(u==0&&v==0) break; else{ st.insert(u); st.insert(v); mx=max(mx, max(u, v)); dis[u][v]=1; } } } for(ll k=1; k<=mx; k++){ for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(ll i=1; i<=mx; i++){ for(ll j=1; j<=mx; j++){ if(dis[i][j]!=1000000009) sum=sum+dis[i][j]; } } sz=st.size(); sz=sz*(sz-1); ans=(double)sum/sz; cout<<"Case "<<cs++<<": average length between pages = "; printf("%.3f clicks\n", ans); st.clear(); } return 0; }