3058305_ac_93ms_2128k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
#define inf -2100000000.00

using namespace std;

int f, m;
double map[501][501];
double dis[501];
int mark[501];

void solve()
{
	int i, j, v;
	double max;

	for(i = 0; i < f; i++)
	{
		dis[i] = inf;
		mark[i] = 0;
	}
	dis[0] = 1.0;
	for(i = 0; i < f; i++)
	{
		max = inf;
		for(j = 0; j < f; j++)
		{
			if(!mark[j]&&dis[j]>max)
			{
				max = dis[j];
				v = j;
			}
		}
		mark[v] = 1;
		for(j = 0; j < f; j++)
		{
			if(map[v][j]!=0&&dis[v]*map[v][j]>dis[j])
			{
				dis[j] = dis[v]*map[v][j];
			}
		}
	}
}

int main()
{
	int i;
	int a, b;
	double w;

	while(scanf("%d",&f)==1,f){
	scanf("%d",&m);
	memset(map,0,sizeof(map));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%lf",&a,&b,&w);
		a--,b--;
		w /= 100;
		if(map[a][b]==0||map[a][b]<w)
		{
			map[a][b] = map[b][a] = w;
		}
	}
	solve();
	printf("%lf percent\n",dis[f-1]*100);}
	return 0;
}