记录编号	328708	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2016-10-24 15:56:02	内存使用	10.09 MiB

/*
	Name: 通信线路
	Copyright: 
	Author: chairman
	Date: 24/10/16 15:57
	Description: prime堆优化get 
*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	int cnt=0;char ch[50];
	while(ch[++cnt]=x%10+48,x/=10);
	while(putchar(ch[cnt]),--cnt);
	putchar('\n');
}
int d[1600][1600],dis[1600],n;
bool vis[1600];
struct node
{
	int x,dis;
	node(int a,int b)
	{
		x=a;dis=b;
	}
	bool operator <(const node & a)const
	{
		return dis>a.dis;
	}
};
void prime()
{
	int ans=0,cnt=0;
	priority_queue<node> q;
	q.push(node(1,0));
	memset(dis,0x7f,sizeof dis);
	dis[1]=0;
	while(!q.empty())
	{
		node t=q.top();q.pop();
		int x=t.x;
		if(vis[x])continue;vis[x]=1;ans+=dis[x];
		cnt++;
		if(cnt==n)break;
		for(int i=1;i<=n;i++)//进行松弛 
			if(!vis[i]&&d[x][i]>-1&&d[x][i]<dis[i])
			{
				dis[i]=d[x][i];
				q.push(node(i,dis[i]));
			}
	}
	write(ans);
}
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			d[i][j]=read();
		}
	}
	prime();
//	system("pause");
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}