#include <iostream>
#include <vector>

using namespace std;

const int INF = 0X7FFFFFFF;

vector<vector<int> > ew;
int n,m;

void INI(void)
{
	ew.assign(n,vector<int>(n,INF));
	for(int i=0;i!=n;++i)
		for(int j=0;j!=n;++j)
			scanf("%d",&(ew[i][j]));
	for(int i=0;i!=n;++i)
		for(int j=i;j!=n;++j) 
			ew[i][j]=ew[j][i] = min(ew[i][j],ew[j][i]);
	scanf("%d",&m);
	for(int i=0;i!=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u,--v;
		ew[u][v] = 0;
	}
}

int Prim(const int root)
{
	vector<bool> InMst(n,false);
	vector<int> d(n,INF);

	d[root] = 0;
	InMst[root] = true;

	for(int i=0;i!=n;++i) {
		d[i] = ew[root][i];
	}

	int ans = 0;
	while(true) {
		int Min = INF;
		int MinPoi = -1;
		for(int i=0;i!=n;++i) {
			if(!InMst[i] && d[i]<Min) {
				Min = d[i];
				MinPoi = i;
			}
		}

		if(MinPoi == -1) {
			break;
		}else {
			ans += Min;
			InMst[MinPoi] = true;
			for(int i=0;i!=n;++i) {
				if(!InMst[i] && ew[MinPoi][i]<d[i])
					d[i] = ew[MinPoi][i];
			}
		}
	}
	return ans;
}


int main(void)
{
	while(1==scanf("%d",&n))
		INI(),printf("%d\n",Prim(0));
	return 0;
}

• Re:怎么就WA？天啊，地啊，牛人说句话啊。 (0) MetalHeart 2008-02-22 21:32:37