记录编号	292897	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-08-09 15:51:21	内存使用	0.84 MiB

#include "fstream"
#include "queue"
using namespace std;
#ifndef M
#define M  305
#endif
ifstream cin("water.in");
ofstream cout("water.out");
int n,ans;
int e[M][M],self[M];
bool book[M];
class P
{
public:
	int /*start ,*/end ,len;
	bool operator <(P p)const
	{
		return len > p.len;
	}
	// P();
	// ~P();
	
};

priority_queue <P> q;

int Prim()
{
	P a;
	for (int i = 2; i <= n; ++i)
	{
		if(e[1][i] /*&& i != 1*/)
		{
			/*a.start = 1;*/
			a.end = i;
			a.len = e[1][i];
			q.push(a);
		}
		/* code */
	}
	book[1] = 1;
	for (int left = n-1;!q.empty()&&left ;)
	{
		P h = q.top();
		q.pop();
		if (book[h.end] == 1)
		{
			continue ;
			/* code */
		}
		ans += h.len;
		left --;
		book[h.end] = 1;
		for (int i = 1; i <= n; ++i)
		{
			P t;
			t.len = e[h.end][i] ;
			t.end = i;
			if (!book[t.end] && e[h.end][i])
			{
				q.push(t);
				/* code */
			}
			/* code */
		}
		/* code */
	}
	return 0;
}
int cyf()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> self[i];
		/* code */
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> e[i][j];
			/* code */
		}
		/* code */
	}
	n++;
		for (int j = 1; j < n; ++j)
		{
			e[n][j] = self[j];
			e[j][n] = self[j];
			/* code */
		}
		/* code */
	
	Prim();
	cout<<ans;
	cin.close();
	cout.close();
	return 0;
}
int CYF=cyf();
int main(int argc, char const *argv[])
{
	/* code */
	/*return 0*/;
}