记录编号	83740	评测结果	AAAAAAAAAA
题目名称	[USACO 3.1] 最短网络	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2013-12-06 10:59:56	内存使用	0.33 MiB

#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fi("agrinet.in");
ofstream fo("agrinet.out");
int n,m;
const int Len=1000+10;
vector<pair<int,int> >A[Len];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
void init();
void Prim();
void COGS_init();
int main()
{
	COGS_init();
	Prim();
	return 0;
}
void init()
{
	int x,y,i,p;
	fi>>n>>m;
	for(i=0;i<m;i++)
	{
		fi>>x>>y>>p;
	    A[x].push_back(make_pair(p,y));
	    A[y].push_back(make_pair(p,x));
	}
}
void COGS_init()
{
	int i,j,p;
	fi>>n;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			fi>>p;
			if(j<i){
				A[i].push_back(make_pair(p,j));
				A[j].push_back(make_pair(p,i));
			}
		}
}
void Prim()
{
	Q.push(make_pair(0,0));
	bool v[Len];int val,Ans=0,i,pos;
	for(i=0;i<n;i++)v[i]=true;
	while(!Q.empty())
	{
		pos=Q.top().second;
		val=Q.top().first;
		Q.pop();
		if(v[pos]==true)
		{
			v[pos]=false;Ans+=val;
			for(i=0;i<A[pos].size();i++)
				Q.push(A[pos][i]);
		}
	}
	fo<<Ans;
}