#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>
using namespace std;

const int maxn = 101;

double pro[maxn][maxn];
int n, m;
double dis[maxn];
bool mark[maxn];

void init()	{
	int i, j, x, y, d;
	cin >> m;
	for (i = 1; i <= m; i ++)	{
		cin >> x >> y >> d;
		pro[x][y] = double(d) / 100;
        	pro[y][x] = double(d) / 100;
	}
}

void work()	{
	int i, j, p;
	double max1;
	
	memset(mark, false, sizeof(mark));
	for (i = 2; i <= n; i ++)	dis[i] = pro[1][i];
	mark[1] = true;	dis[1] = 1;
	for (i = 2; i <= n; i ++)	{
		max1 = 0;	p = 0;
		for (j = 1; j <= n; j ++)
			if ((!mark[j]) && (dis[j] > max1))	{
				max1 = dis[j];
				p = j;
			}
		if (p == 0)	break;
		mark[p] = true;
		for (j = 1; j <= n; j ++)
			if ((!mark[j]) && (dis[p] * pro[p][j] > dis[j]))
				dis[j] = dis[p] * pro[p][j];
	}
}

void print()	{
	printf("%.6f percent\n", dis[n] * 100);
}

int main()	{
	for (cin >> n; n != 0; cin >> n)	{
		init();
		work();
		print();
	}
	return 0;
}

• Re:WHY I got WA? (696) pb128 2005-07-19 23:45:19
  • Re:WHY I got WA? (21) zzyzzy12 2010-09-23 03:18:07