记录编号	385126	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-03-20 11:09:01	内存使用	0.26 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MAXN 10000+10

inline int in(void){
	char tmp = getchar();
	int res = 0, f = 1;
	while(!(is_num(tmp) || tmp == '-'))tmp = getchar();
	if(tmp == '-')f=-1, tmp = getchar();
	while(is_num(tmp))
		res = (res<<1) + (res<<3) + (tmp^48),
		tmp = getchar();
	return res * f;
}

struct DATA{
	int to;
	double k;
	
	DATA(int a, int b){
		to=a, k=b*1.0/100;
	}
};

double SPFA(int sta, int end);

vector<DATA>Map[MAXN];
queue<int>que;
int N, M;
int a, b, c;
bool exist[MAXN];
double dis[MAXN];

void *Main(void){
#ifndef LOCAL
	freopen("toura.in", "r", stdin);
	freopen("toura.out", "w", stdout);
#endif

	N=in(), M=in();
	for(int i=1; i<=M; ++i){
		a=in(), b=in(), c=in();
		Map[a].push_back(DATA(b, c));
		Map[b].push_back(DATA(a, c));
	}
	printf("%.6lf", SPFA(1, N));
	return NULL;
}
void *Main_(Main());
int main(){;}

double SPFA(int sta, int end){
	int now, to;
	double v, tmp;
	
	memset(dis, -127, sizeof(dis));
	memset(exist, 0, sizeof(exist));
	
	dis[sta]=1;
	que.push(sta);
	exist[sta]=true;
	
	while(!que.empty()){
		now=que.front();
		que.pop();
		exist[now]=false;
		for(int i=0; i<Map[now].size(); ++i){
			to = Map[now][i].to, v = Map[now][i].k;
			if((tmp=dis[now]*v)>dis[to]){
				dis[to]=tmp;
				if(!exist[to]){
					que.push(to);
					exist[to]=true;
				}
			}
		}
	}
	return dis[end]*100;
}