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;

}

}

### Like this:

Like Loading...