学步园

#include <iostream>
#include <cstdio>
#include <cstring>
const int INF=1000000000;
const int maxn=510;
using namespace std;

int map[maxn][maxn],dis[maxn],visited[maxn];
int main()
{
	int n,a,b,k,i,j,N,E,mindistance,min,t;
	scanf("%d",&n);
	while (n--)
	{
		memset(visited,0,sizeof(visited));
		mindistance=0;
		scanf("%d%d",&N,&E);
		for (i=0;i<N;i++)
		{
			for (j=0;j<N;j++)
			{
				map[i][j]=INF;
			}
		}
		for (i=0;i<E;i++)
		{
			scanf("%d%d%d",&a,&b,&k);
			map[a][b]=map[b][a]=k;
		}
		for (j=0;j<N;j++)
		{
			dis[j]=map[0][j];//初始化最短距离
		}
		visited[0]=1;//标记已经连接此点
		for (i=0;i<N;i++)
		{		
			min=INF;
			for (j=0;j<N;j++)
			{
				if(!visited[j] && min>dis[j])
				{
					min=dis[j];
					t=j;
				}
			}
			if(min!=INF)//值得注意的地方
				mindistance+=min;//总耗费
			visited[t]=1;
			for (j=0;j<N;j++)
			{
				if (!visited[j] && dis[j]>map[t][j])
				{
					dis[j]=map[t][j];//更新已连接的点与各无连接的点的最短距离
				}
			}
		}
		printf("%d\n",mindistance);
	}
	return 0;
}

Sample Input

1
3 3
0 1 5
0 2 0
1 2 9

Sample Output

5