记录编号	190398	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	Dissolute丶Tokgo	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2015-10-03 08:17:32	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;

struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
	bool operator < (const Edge& x) const{
		return dist>x.dist;
	}
};

int n,fa[303];
priority_queue<Edge>Q;

inline int qread(){
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret;
}

int getf(int x){
	return x==fa[x]?x:fa[x]=getf(fa[x]);
}

int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	int w;
	n=qread();
	rep(i,1,n){
		w=qread();
		Q.push(Edge(0,i,w));
	}
	rep(i,1,n) rep(j,1,n){
		w=qread();
		if(i!=j) Q.push(Edge(i,j,w));
	}
	int ans=0,cnt=0,u,v;
	rep(i,1,n) fa[i]=i;
	while(cnt!=n){
		Edge e=Q.top();
		Q.pop();
		u=getf(e.from);
		v=getf(e.to);
		if(u!=v){
			fa[u]=v;
			ans+=e.dist;
			cnt++;
		}
	}
	printf("%d",ans);
//	while(1);
}