记录编号	514178	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2018-10-14 17:03:42	内存使用	0.60 MiB

#include<bits/stdc++.h>
using namespace std;
queue<int> que;
struct node
{ int t;
  double dist;
};
vector<node> g[10010];
double d[10010];
int m,n,te,tc,ts;
bool inque[100001];
void spfa(int s)
{ memset(d,0,sizeof(d));
  memset(inque,0,sizeof(inque));
  double maxx;
  d[1]=1;que.push(1); 
  while(!que.empty())
  { int u=que.front();
    que.pop();
    inque[u]=false;
    for(int i=0;i<g[u].size();i++)
     { int v=g[u][i].t;
       double w=g[u][i].dist;
       if(d[u]*w>d[v]) { d[v]=d[u]*w;
                         if(inque[v]==false)
                             { que.push(v);
                               inque[v]=true;}
                       } 
     }
  }
}
int main()
{ freopen("toura.in","r",stdin);
  freopen("toura.out","w",stdout);
  int x,y;
  double z;
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++)
  { scanf("%d%d%lf",&x,&y,&z);
    z=z/100;
    g[x].push_back((node){y,z});
    g[y].push_back((node){x,z});
  }
  spfa(1);
  printf("%.6lf",d[n]*100);
  return 0;
}