pku2472.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 110
double perc[size][size];
double max[size];
int visited[size];
int N;

void Solve()
{
	int k, i, j, u;
	int p, s, e;
	double maxp;
	scanf("%d", &k);
	memset(perc, 0, sizeof(perc));
	while (k--)
	{
		scanf("%d%d%d", &s, &e, &p);
		perc[s - 1][e - 1] = p / 100.0;
		perc[e - 1][s - 1] = p / 100.0;
	}
	memset(visited, 0, sizeof(visited));
	for (i = 0; i < N; i++)
	{
		max[i] = perc[i][0];
	}
	visited[0] = 1;
	while (1)
	{
		u = -1;
		maxp = 0;
		for (i = 0; i < N; i++)
		{
			if (!visited[i] && maxp < max[i])
			{
				maxp = max[i];
				u = i;
			}
		}
		if (u == -1)
		{
			break;
		}
		visited[u] = 1;
		for (i = 0; i < N; i++)
		{
			if (!visited[i] && max[i] < max[u] * perc[u][i])
			{
				max[i] = max[u] * perc[u][i];
			}
		}
	}
	printf("%.6lf percent\n", max[N - 1] * 100);
}

int main()
{
	while (scanf("%d", &N) != -1 && N)
	{
		Solve();
	}
	return 0;
}