记录编号	387730	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2017-03-27 13:56:42	内存使用	1.58 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#define MAXN
using namespace std;
inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
/*-----------------------------------------------------------------------------*/

struct edge{
	int fr, to, ne;
	double tr;
}e[60233];

queue<int> zz;

int en, n, m, he[10233];
double dis[10233];

int main() {
#ifndef MYLAB
	freopen("toura.in", "r", stdin);
	freopen("toura.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif

	n = read();
	m = read();
	
	for(int i = 0; i < m; i++) {
		int x = read();
		int y = read();
		double z;
		cin >> z;
		e[++en].ne = he[x];
		he[x] = en;
		e[en].fr = x;
		e[en].to = y;
		e[en].tr = z / 100;
		
		e[++en].ne = he[y];
		he[y] = en;
		e[en].fr = y;
		e[en].to = x;
		e[en].tr = z / 100;
	}

	zz.push(1);
	dis[1] = 100;
	while(!zz.empty()) {
		int x = zz.front();
		zz.pop();
		for(int i = he[x];i; i = e[i].ne) {
			int y = e[i].to;
			double z = e[i].tr;
			if(dis[x] * z > dis[y]) {
				dis[y] = dis[x] * z;
				zz.push(y);
			}
		}
	}

	printf("%.6lf", dis[n]);

	return 0;
}