记录编号	329007	评测结果	AAAAAAAAAA
题目名称	通信线路	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	1.148 s
提交时间	2016-10-24 19:43:09	内存使用	77.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=2500+100;
int n,dis[maxn];
bool flag[maxn];
struct E{
	int to,next,w;
};E e[maxn*maxn];
int head[maxn],len=0;
inline void link(const int& from,const int& to,const int&w){
	e[++len].to=to;
	e[len].w=w;
	e[len].next=head[from];
	head[from]=len;
}
struct node{
	int id,lowcost;
	bool operator<(const node &s)const{
		return lowcost>s.lowcost;
	}
	node(const int &i=0,const int &l=0){
		id=i;lowcost=l;
	}
};node u;priority_queue<node>q;
inline int  MST(){
	int mst=0;
	memset(dis,0x3f,sizeof dis);
	memset(flag,0,sizeof flag);
	q.push(node(1,0));
	dis[1]=0;
	while(!q.empty()){
		u=q.top();q.pop();
		if(dis[u.id]!=u.lowcost)continue;
		flag[u.id]=1;
		mst+=u.lowcost;
		for(int i=head[u.id];i!=-1;i=e[i].next){
			if(e[i].w<dis[e[i].to]&&!flag[e[i].to]){
				dis[e[i].to]=e[i].w;
				q.push(node(e[i].to,dis[e[i].to]));
			}
		}
	}
	return mst;
}
int main(){
	#define submit
	#ifdef submit
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	#endif
	scanf("%d",&n);
	int tmp;
	memset(head,-1,sizeof head);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&tmp);
			if(tmp!=-1)link(i,j,tmp);
		}
	}
	printf("%d\n",MST());
	#ifndef submit
	system("pause");
	#else
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
}