记录编号	430525	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-07-29 21:23:48	内存使用	0.89 MiB

#include <fstream>
#include "vector"
#include "queue"
#include<iomanip>

using namespace std;
ifstream cin("toura.in");
ofstream cout("toura.out");
int n,m;
double dis[10005];
bool book[100005];
class Point
{
public:
	// point();
	// ~point();
	int another;

	double cost;
	// point():cost(0){}	
};
vector<Point> v[10006];
queue<int> q;
void spfa()
{
	book[1] = 1;
	q.push(1);
	while(!q.empty())
	{
		int h = q.front();
		q.pop();
		book[h] = 0;
		for (int i = 0; i < v[h].size(); ++i)
		{
			if (v[h][i].cost*dis[h] > dis[v[h][i].another])
			{
				dis[v[h][i].another] = v[h][i].cost*dis[h];
				if(book[v[h][i].another] == 0)
				{
					q.push(v[h][i].another);
					book[v[h][i].another] = 1;
				}
				
				/* code */
			}
			/* code */
		}

	}

}
int cyf()
{
	int i,j,k;
	cin >> n >> m;
	dis[1] = 1;
	for (int i = 1; i <= m; ++i)
	{
		int t1,t2,t3;
		Point l;
		cin >> t1 >> t2 >> t3;
		l.another = t2;
		l.cost = t3 / 100.0;
		v[t1].push_back(l);
		l.another = t1;
		v[t2].push_back(l);
		/* code */
	}
	spfa();
	
	cout<<setiosflags(ios::fixed)<<setprecision(6)<<dis[n]*100<<endl;
	cin.close();				
	cout.close();
	return 0;
}
int hhhh = cyf();
int main() {;}