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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=2500+100;
int G[maxn][maxn],n,dis[maxn];
bool flag[maxn];
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(n,0));dis[n]=0;
	for(int j=1;j<=n;++j){
		if(q.empty())return -1;
		u=q.top();q.pop();
//		if(flag[u.id])continue;
		flag[u.id]=1;
		mst+=u.lowcost;
		for(int i=1;i<=n;++i){
			if(G[u.id][i]<dis[i]&&!flag[i]){
				dis[i]=G[u.id][i];
				q.push(node(i,dis[i]));
			}
		}
	}
	return mst;
}
int main(){
	#define submit
	#ifdef submit
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	#endif
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&G[i][j]);
			if(G[i][j]==-1)G[i][j]=0x3f3f3f3f;
		}
	}
	printf("%d\n",MST());

	#ifndef submit
	system("pause");
	#else
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
}