记录编号	235622	评测结果	AAAAAAAAAA
题目名称	新的开始	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2016-03-11 10:32:07	内存使用	0.66 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff
using namespace std;
const int maxn=310;
int e[maxn][maxn],n;
int lowcost[maxn],closest[maxn];
bool ok[maxn];
int prim();
int main(){
#define COGS
#ifdef COGS
	freopen("newstart.in","r",stdin);
	freopen("newstart.out","w",stdout);
#endif
	scanf("%d",&n);
	//for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)e[i][j]=INF;
	for(int i=1;i<=n;i++)scanf("%d",&e[n+1][i]),e[i][n+1]=e[n+1][i];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&e[i][j]),e[j][i]=e[i][j];
	n++;
	printf("%d\n",prim());
#ifdef COGS
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}
int prim(){
	int result=0,min;
	for(int i=1;i<=n;i++)lowcost[i]=e[1][i];
	memset(closest,0,sizeof(int)*(n+5));
	memset(ok,0,sizeof(bool)*(n+5));
	ok[1]=true;
	for(int i=1;i<n;i++){
		min=INF;
		int x;
		for(int j=1;j<=n;j++)if(!ok[j]&&lowcost[j]<min)min=lowcost[j],x=j;
		ok[x]=true;
		result+=lowcost[x];
		for(int j=1;j<=n;j++)if(!ok[j]&&lowcost[j]>e[x][j])lowcost[j]=e[x][j];
	}
	return result;
}