记录编号	53755	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2013-03-05 11:09:31	内存使用	12.20 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
	int s,nex;
}a[40100];
struct edge{
	int y,nex;
	double v;
}e[800000];
int n,m,p;
double dis[40010];
bool f[40010];
int queue[100000];
void SPFA(){
	int s=1;
	int t;
	int tmp;
	memset(f,true,sizeof(f));
	memset(dis,0,sizeof(dis));
	memset(queue,0,sizeof(queue));
	f[s]=false;
	dis[s]=1;
	int head=0;
	int tail=1;
	queue[tail]=s;
	while (head<=tail){
		head++;
		tmp=queue[head];
		f[tmp]=true;
		t=a[tmp].nex;
		for (int i=1;i<=a[tmp].s;i++){
			if (dis[tmp]*e[t].v>dis[e[t].y]){
				dis[e[t].y]=dis[tmp]*e[t].v;
				if (f[e[t].y]){
					f[e[t].y]=false;
					queue[++tail]=e[t].y;
				}
			}
			t=e[t].nex;
		}
	}
}
void add(int x,int y,int v){
	p++;
	double tmp;
	tmp=v;
	tmp/=100;
	a[x].s++;
	e[p].y=y;
	e[p].v=tmp;
	e[p].nex=a[x].nex;
	a[x].nex=p;
}
void init(){
	freopen("toura.in","r",stdin);
	freopen("toura.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,v;
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&v);
		add(x,y,v);
		add(y,x,v);
	}
}
void work(){
	SPFA();
	dis[n]*=100;
	printf("%.6lf",dis[n]);
}
int main(){
	init();
	work();
	return 0;
}