NYOJ 布线问题（prime 算法基础）

http://59.69.128.200/JudgeOnline/problem.php?pid=38

#include <iostream>
#include<cstdio>
#include<string.h>
#include<vector>
using namespace std;
const int MAX=999999;
int n,v,lowcost[505],cost;
int mat[505][505],visit[505];
void prime()
{
	for(int i=1;i<=v;i++)
	{
		int temp=lowcost[i],k=i;
		for(int j=1;j<=v;j++)
		{
			if(lowcost[j]<temp)
			{
				temp=lowcost[j];
				k=j;
			}
		}
		cost+=temp;
		lowcost[k]=MAX;
		for(int j=1;j<=v;j++)
			if(lowcost[j]<MAX&&lowcost[j]>mat[k][j])
				lowcost[j]=mat[k][j];
	}
}
int main()
{
	//freopen("1.txt","r",stdin);
	scanf("%d",&n);
	int e;
	while(n--)
	{
		cost=0;
		scanf("%d%d",&v,&e);
		while(e--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			mat[b][a]=mat[a][b]=c;
		}
		for(int i=1;i<=v;i++)
		{
			scanf("%d",&mat[0][i]);
			lowcost[i]=mat[0][i];
		}
		prime();
		printf("%d\n",cost);
	}

}