记录编号	105701	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.410 s
提交时间	2014-06-12 08:37:59	内存使用	8.93 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

#define  maxn  1502
#define  Max   0x7f7f7f7f

using namespace std;

int Gra[maxn][maxn];
int Min[maxn];
bool Exi[maxn];

int n ;

int main()
{
	freopen("mcst.in" ,"r",stdin );
	freopen("mcst.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1 ; i <= n ; i ++ )
	{
		for (int j = 1 ; j <= n ; j ++ )
		{
			int t ;
			scanf("%d",&t);
			if (t != -1) Gra[i][j] = t ;
			else Gra[i][j] = Max ;
		}
	}
	memset(Exi,0,sizeof(Exi));
	memset(Min,0x7f,sizeof(Min));
	Min[1] = 0;
	for (int i = 1 ; i <= n ; i ++ )
	{
		int k = 0 ;
		for (int j = 1 ; j <= n ; j ++ )
		{
			if (!Exi[j] && (Min[j] < Min[k])) k = j ;
		}
		Exi[k] = true ;
		for (int j = 1 ; j <= n ; j ++ )
		{
			if (!Exi[j] && (Gra[k][j] < Min[j])) Min[j] = Gra[k][j] ;
		}
	}
	int tot = 0 ;
	for (int i = 1 ; i <= n ; i ++ ) tot += Min[i] ;
	printf("%d\n",tot) ;
	return 0;
}