#include<stdio.h>

#define max 1001
#define num 100

int sum,cost[num][num],lowcost[num],closest[num];

int cases,cnum;

void init()
{
	int i,j,p,q;
	for( i=1; i<=cases; i++ )
		for( j=1; j<=cases; j++ )
			scanf("%d",&cost[i][j]);
	scanf("%d",&cnum);
	for( i=1; i<=cnum; i++ )
	{
		scanf("%d%d",&p,&q);
		cost[p][q]=cost[q][p]=0;
	}
	sum=0;
}

void prime()
{
  int i,j,k=0;
  int v0=1;
  int min;
  for( i=1; i<=cases; i++ )
  {
	  lowcost[i]=cost[v0][i];
	  closest[i]=v0;
  }
  lowcost[v0]=-1;
  for( i=1; i<cases; i++ )
  {
	  
	  min=max;
	  for( j=1; j<=cases; j++ )
	  {
		  if( lowcost[j]<min  && lowcost[j]!=-1)
		  {
			  min=lowcost[j];
			  k=j;
		  }	
	  }
		
	    sum+=lowcost[k];
		//printf("sum=%d\n",sum);
		//printf("k=%d\n",k);
	    lowcost[k]=-1;
	 for( j=1; j<=cases; j++ )
	 {
	    if( cost[k][j]<lowcost[j] && lowcost[j]!=-1  )
		{
			lowcost[j]=cost[k][j];
			closest[j]=k;
		}
	 }
  }
}


int main()
{
	while( scanf("%d",&cases)==1 )
	{
		init();
		prime();
		printf("%d\n",sum);
	}
	return 0;
}

/*
 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2
1 2
3 4
*/

• 想法对的（我刚刚实现了）。。程序有问题～～ (0) winsweet 2008-06-03 22:57:52