#include <stdio.h>
long int dist[1005][1005];
long int low[1005];
int sce,m,n;
const long int MAX=10000000;
int  prim_1()
{
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		low[i]=dist[1][i];
	}
	low[1]=0;
	for (int i=1;i<=n;i++)
	{
		long int MIN=MAX;
		int t=0;
		for (int j=1;j<=n;j++)
		{
			if((low[j]!=0)&&(low[j]<MIN))
			{
				MIN=low[j];
				t=j;
				ans=MIN;
			}
		}
		if (t)
		{
			low[t]=0;
			for(int j=1;j<=n;j++)
			{
				if (low[j]&&dist[t][j]<low[j])
				{
					low[j]=dist[t][j];
				}
			}
		}
		else return ans;
	}
	return ans;
}
int main()
{
	//freopen("C:/Users/bohu/Desktop/a.in","r",stdin);
	int t1,t2;
	scanf("%d",&sce);
	for(int i=1;i<=sce;i++)
	{
		scanf("%d%d",&n,&m);
		for (int j=1;j<=n;j++)
		{
			for(int h=1;h<=n;h++)
				dist[j][h]=MAX;
		}
		for (int j=1;j<=m;j++)
		{
			scanf("%d%d",&t1,&t2);
			scanf("%ld",&dist[t1][t2]);
			dist[t2][t1]=dist[t1][t2];
		}
		printf("Scenario #%d:\n",sce);
		printf("%ld\n\n",prim_1());


	}
	//fclose(stdin);
	return 0;
}

• Re:改成这样了 还不行 (1066) tangbohu222 2011-04-02 21:08:29