记录编号	352294	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	0.451 s
提交时间	2016-11-17 07:09:01	内存使用	9.00 MiB

#include <stdio.h>
int a[1510][1510],book[1510],dis[1510],n,j,i,count,sum,min,e;
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]==-1)
				a[i][j]=0x7f7f7f7f;
		}
	for(i=1;i<=n;i++)
	{
		a[i][i]=0;
		dis[i]=a[1][i];
	}
	book[1]=1;
	count=1;
	sum=0;
	while(count<n)
	{
		min=0x7f7f7f7f;
		for(i=1;i<=n;i++)
			if(!book[i]&&dis[i]<min)
			{
				min=dis[i];
				j=i;
			}
		book[j]=1;
		count++;
		sum+=dis[j];
		for(i=1;i<=n;i++)
			if(!book[i]&&dis[i]>a[j][i])
				dis[i]=a[j][i];
	}
	printf("%d",sum);
	
	
	return 0;
}