记录编号	77171	评测结果	AAAAAAAAAA
题目名称	新的开始	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2013-11-01 14:48:00	内存使用	0.66 MiB

#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("newstart.in");
ofstream fout("newstart.out");
const int INF=999999999;
int N,ANS=INF,P=0;
int map[302][302],a[303];//存图
int dis[302];//每个节点到MST的最短距离
bool flag[302]={0};//是否加入MST
int father[302];
int Prim()
{
	int i,j,s,u;
	int temp=0;
	for(i=1;i<=N+1;i++)
	{
		s=INF;
		for(j=1;j<=N+1;j++)//找出离MST最小的点加入
		{
			if(flag[j]==0&&dis[j]<s)
			{
				s=dis[j];
				u=j;
			}
		}
		flag[u]=1;temp+=s;
		for(j=1;j<=N+1;j++)
		{
			if(flag[j]==0&&dis[j]>map[u][j])
			{
				dis[j]=map[u][j];
			}
		}
	}
	return temp;
}
int main()
{
	fin>>N;
	int i,j,temp;
	for(i=1;i<=N;i++)
	{
		fin>>a[i];
		map[N+1][i]=a[i];
		map[i][N+1]=a[i];
	}
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			fin>>temp;
			map[i][j]=temp;
		}
	memset(dis,63,sizeof(dis));
	dis[1]=0;
	fout<<Prim()<<endl;
	return 0;
}