2472.cpp

这些是我到目前在PKU上做出的题目

#include <stdio.h>

bool s[101][101];
double k[101][101],t,f[101];
int n,m,i,j,a1,a2;

void play(int now)
{
	bool ok[101];
	int i;
	for (i=1;i<=n;i++)
		ok[i]=0;
	if (now!=n)
	{
		for (i=1;i<=n;i++)
			if (s[now][i])
				if (f[now]*k[now][i]/100.0>f[i])
				{
					f[i]=f[now]*k[now][i]/100.0;
					ok[i]=1;
				}
		for (i=1;i<=n;i++)
			if (ok[i])
				play(i);
	}
}

int main()
{
	scanf("%d",&n);
	while (n!=0)
	{
		scanf("%d",&m);
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				s[i][j]=0;
		for (i=1;i<=n;i++)
			f[i]=0;
		f[1]=100;
		for (i=1;i<=m;i++)
		{
			scanf ("%d %d %lf",&a1,&a2,&t);
			s[a1][a2]=1;
			s[a2][a1]=1;
			k[a1][a2]=t;
			k[a2][a1]=t;
		}
		play(1);
		printf("%.6f percent\n",f[n]);
		scanf("%d",&n);
	}
	return 0;
}