CHICAGO 106 miles to Chicago

Problem Link

#Algo: Floyd Warshal

#include<bits/stdc++.h>
double a[105][105];
using namespace std;
int main()
{
int n,e;

while(cin>>n &&n)
{
cin>>e;
memset(a,0,sizeof a);
for(int i=0;i<e;i++)
{
int u,v;
double c;
cin>>u>>v>>c;
a[u][v]=a[v][u]=c/100.0;
}
for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=max(a[i][j],a[i][k]*a[k][j]);
cout<<setprecision(6)<<fixed<<a[1][n]*100<<” percent”<<endl;
}
}

 

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in spoj, Uncategorized 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