记录编号	119374	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.784 s
提交时间	2014-09-12 16:38:33	内存使用	15.94 MiB

#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream in("mcst.in");
ofstream out("mcst.out");
struct www{
	int zhi;
	int to;
	www(){zhi=0;to=0;} 
	bool operator<( const www &x ) const {return zhi>x.zhi;}
};
www s[1510][1510],miku;
int n,i,l,zj,shu[1510]={0},aiky=0;
long long k=0;
bool pan[1510]={0};
priority_queue<www> A;
int main()
{
	in>>n;
	for(i=1;i<=n;i++)
	for(l=1;l<=n;l++)
	{
		in>>zj;
		if(zj!=-1)
		{
			shu[i]++;
			s[i][ shu[i] ].zhi=zj;
			s[i][ shu[i] ].to=l;
		}
	}
	pan[1]=true;
	aiky=1;
	for(i=1;i<=shu[1];i++) A.push(s[1][i]);
	while(aiky!=n)
	{
		miku=A.top();
		A.pop();
		zj=miku.to;
		if(!pan[zj])
		{
			pan[zj]=true;
			k+=miku.zhi;
			aiky++;
			for(i=1;i<=shu[zj];i++)
			if(!pan[s[zj][i].to])
			A.push(s[zj][i]);
		}
	}
	out<<k<<endl;
	in.close();
	out.close();
	return 0;
}