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

## 纪念一百题，水水的！

Posted by 15310320305 at 2017-02-07 14:46:06 on Problem 2472
```#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n,m,e;
int hed[105],vis[105];
double dis[105];

struct st{
int v,nex;
double w;
}edge[20005];

edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
}
double spfa(){
for(int i=1;i<=n;i++)dis[i]=0.0,vis[i]=0;dis[1]=1;
priority_queue<pair<double,int> >q;
q.push(make_pair(dis[1],1));
while(!q.empty()){
int u = q.top().second;q.pop();
if(vis[u])continue;vis[u]=1;
for(int i=hed[u];~i;i=edge[i].nex){
int v = edge[i].v;
if(dis[v]<dis[u]*edge[i].w){
dis[v]=dis[u]*edge[i].w;
if(!vis[v])
{
q.push(make_pair(dis[v],v));
}
}
}
}
return dis[n]*100.0;
}

int main()
{
while(cin>>n,n){
cin>>m;
memset(hed,-1,sizeof(hed));
e=1;
while(m--){
int u,v;scanf("%d%d",&u,&v);
double w;scanf("%lf",&w);
w=w/100.0;
}
printf("%.6lf percent\n",spfa());

}
return 0;
}```

Followed by: