#include<stdio.h>
#include<string.h>

long u[1001][1001],s[1001];
long ll[1001],mm[1001];
long f[1001],min;
bool uu[1001];

int main()
{
	int n,t,i,a,b,l,j;
	bool flag;
	scanf("%d%d",&t,&n);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			u[i][j]=100000001;
	for (i=1;i<=t;i++)
	{
		scanf("%d%d%ld",&a,&b,&min);
		if (u[a][b]>min)
		{
			u[a][b]=min;
		    u[b][a]=min;
		}
	}
	l=1;
	s[1]=n;
	f[1]=0;
	flag=true;
	memset(uu,true,sizeof(uu));
	uu[n]=false;
	mm[1]=100000001;
	for (i=1;i<=n-1;i++)
		if (mm[1]>u[n][i])
		{
			mm[1]=u[n][i];
			ll[1]=i;
		}
	while (flag)
	{
		min=100000001;
		for (i=1;i<=l;i++)
			if (mm[i]<min)
			{
				a=i;
				b=ll[i];
				min=mm[i];
			}
		l++;
		s[l]=b;
		uu[b]=false;
		f[l]=f[a]+min;
		for (i=1;i<=l-1;i++)
			if (ll[i]==b)
			{
				mm[i]=100000001;
				for (j=1;j<n;j++)
					if (uu[j]&&u[s[i]][j]<mm[i])
					{
						mm[i]=u[s[i]][j];
				        ll[i]=j;
					}
			}
		mm[l]=100000001;
		for (i=1;i<n;i++)
			if (uu[i]&&u[b][i]<mm[l])
			{
				mm[l]=u[b][i];
				ll[l]=i;
			}
		if (b==1) flag=false;
	}
	printf("%ld\n",f[l]);
	return 0;
}

• 怎么没人理我哦?sempr呢?styc在吗? (0) lxhgww 2006-12-01 22:05:59
  • 不看代码 (0) frkstyc 2006-12-01 22:07:54