821 – Page Hopping

Problem Link

#Solution

 

#include <iostream>
using namespace std;
int ad[110][110];
#define inf 100000

int main() {

int a,b,n,cs=1;

while(cin>>a>>b &&a &&b)
{
n=max(a,b);

for(int i=0;i<110;i++)
for(int j=0;j<110;j++)
if(i==j) ad[i][j]=0;
else ad[i][j]=inf;
ad[a][b]=1;
while(cin>>a>>b)
{
if(a==0 &&b==0)
break;
n=max(n,max(a,b));
ad[a][b]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ad[i][j]=min(ad[i][j],ad[i][k]+ad[k][j]);

int sum=0,co=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)

if(ad[i][j] &&ad[i][j]<inf) {sum+=ad[i][j];
co++;}
printf(“Case %d: average length between pages = %.3lf clicks\n”,cs++,double(sum)/(double)co);
}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in uva and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s