#include<stdio.h>
#include<string.h>
#include<math.h>
int a[2300][2300],d[2300],min,MAX=0;
int main()
{
	int n,m,v[2300],i,j,l,minj;
	scanf("%d%d",&n,&m);
	memset(a,-1,sizeof(a));
	while(m--)
	{
		scanf("%d%d%d",&i,&j,&l);
		if(l<a[i][j]||a[i][j]<0)
		{
			a[i][j]=l;
			a[j][i]=a[i][j];
		}
	}
	memset(v,0,sizeof(v));
	v[1]=1;
	for(i=1;i<=n;i++) d[i]=a[1][i];
	for(i=2;i<=n;i++)
	{
		min=1000000001;
		for(j=1;j<=n;j++)
		{
			if(!v[j]&&d[j]<min)
			{
				min=d[j];
				minj=j;
			}
		}
		v[minj]=1;
		if(min>MAX) MAX=min;
		for(j=1;j<=n;j++)
		{
			if(!v[j]&&a[minj][j]<d[j]) d[j]=a[minj][j];
		}
	}
	printf("%d\n",MAX);
	return 0;
}

• 没人来么。。。 (1) newfolder 2010-03-25 23:08:03
• Re:PRIM算法WA!!!!代码不长..麻烦高手帮我看看。谢了。。 (30) fyq 2010-05-08 22:03:16