记录编号	23607	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.239 s
提交时间	2011-03-16 13:17:09	内存使用	0.25 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;

typedef struct LIST_NODE {
	short end, p;
	LIST_NODE *next;
} *GLIST;

GLIST *lk;

inline void addway (const short a, const short b, const short p)
{
	LIST_NODE *newnode = (LIST_NODE*)malloc(sizeof(LIST_NODE));
	newnode->end = b;
	newnode->p = p;
	newnode->next = lk[a];
	lk[a] = newnode;
}

int main ()
{
	FILE *fin = fopen("toura.in", "r"),
		 *fout = fopen("toura.out", "w");

	short M, N;
	fscanf(fin, "%hd%hd", &N, &M);
	
	lk = (GLIST*)malloc(N*sizeof(GLIST));
	memset(lk, 0, N*sizeof(GLIST));
	for (short i=0; i<M; i++)
	{
		short a, b, p;
		fscanf(fin, "%hd%hd%hd", &a, &b, &p);
		addway(a-1, b-1, p);
		addway(b-1, a-1, p);
	}

	queue<int> q;
	double dist[N];
	bool boo[N];
	memset(dist, 0, sizeof(dist));
	memset(boo, 0, sizeof(boo));

	boo[0] = true;
	dist[0] = 100.0;
	q.push(0);
	while (!q.empty())
	{
		int curr = q.front();
		q.pop();

		for (LIST_NODE *pi=lk[curr]; pi; pi=pi->next)
		{
			double k;
			if ((k = dist[curr]*(pi->p)/100.0) > dist[pi->end])
			{
				dist[pi->end] = k;
				if (!boo[pi->end])
					q.push(pi->end);
			}

		}

		boo[curr] = false;
	}

	fprintf(fout, "%.6lf\n", dist[N-1]);

	fclose(fin);
	fclose(fout);

	return 0;
}