CHICAGO - 106 miles to Chicago editorial or solution spoj - UCS - Unleash-Coding-Skills

Saturday, 14 April 2018

CHICAGO - 106 miles to Chicago editorial or solution spoj - UCS

CHICAGO - 106 miles to Chicago

Problem Link:
http://www.spoj.com/problems/CHICAGO/

Notes:
1) Take care while taking input in CHICAGO - 106 miles to Chicago problem.
2) Take care that cost of edge is given in percent modify from number to percent or probability and vice versa as required.
3) Take care while printing output we should also print "percent" in output.
4) Take care about printing the final distance it should have precision up to 6 digits in problem CHICAGO - 106 miles to Chicago .

This is simply implementation of floyd warshall algorithm.This is one of example problem for floyd warshal algorithm.It is one of the example of graphs problem.

The solution for the problem CHICAGO - 106 miles to Chicago spoj is
#include<bits/stdc++.h>

using namespace std;
int main()
{
double arr[105][105];
int n,e;

while(cin>>n &&n)
{
cin>>e;
memset(arr,0,sizeof arr);
for(int i=0;i<e;i++)
{
int u,v;
double c;
cin>>u>>v>>c;
arr[u][v]=arr[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++)
arr[i][j]=max(arr[i][j],arr[i][k]*arr[k][j]);
cout<<setprecision(6)<<fixed<<arr[1][n]*100<<" percent"<<endl;
}
}

Happy Coding........

Feel Free to comment for doubts............

No comments:

Post a comment