Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 太水了。。。。贴代码。。FLoyd+精度。。

Posted by 351200 at 2011-10-08 20:08:31 on Problem 2472
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

using namespace std;
const int MAXN=101 ;
int N,M ;
double map[MAXN][MAXN] ;
double Max(double x,double y)
{
return x>y ? x: y ;
}
double Mul(double x,double y)
{
return x*y ;
}
void Floyd()
{
int i,j,k ;
for(k=1 ;k<=N ;k++)
for(i=1 ;i<=N ;i++)
for(j=1;j<=N ;j++)
{
if(map[i][k]!=0 && map[k][j]!=0)
map[i][j]=Max(map[i][j],Mul(map[i][k],map[k][j])) ;
}
}
int main()
{
//  freopen("in.txt","r",stdin) ;
int i ;
while(cin>>N && N)
{
cin>>M ;
memset(map,0.0,sizeof(map)) ;
for(i=0 ;i<M ;i++)
{
int u,v ;
double w ;
cin>>u>>v>>w ;
map[u][v]=w*0.01 ;
map[v][u]=w*0.01 ;
}
Floyd() ;
printf("%.6lf ", map[1][N]*100) ;
cout<<"percent"<<endl ;
}
return 0;
}

Followed by: