#include<stdio.h>
#include<string.h>
int main(void){
	int n;                               //村庄的数量
	int distance[100][100];                //村庄之间的距离
	int i,j;                             //计数
	int sum=0;                             //记录总路程
	int d[100];                            //记录暂时的最短距离
	scanf("%d",&n);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&distance[i][j]);
	int q;                               //道路的数量
	int k;                               //计数
	scanf("%d",&q);
	for(k=0;k<q;k++){
		scanf("%d%d",&i,&j);
		distance[i-1][j-1]=0;
		distance[j-1][i-1]=0;
	}
	int used[100];                        //记录每个村庄是否被录入
	memset(used,0,sizeof(used));
	used[0]=1;
	for(i=0;i<n;i++)
		d[i]=distance[0][i];
	for(i=0;i<n-1;i++){
		int min=1000;
		int tag;
		for(j=0;j<n;j++){
			if(used[j]==0&&d[j]<min){
				min=d[j];
				tag=j;
			}
		}
		used[tag]=1;
		sum+=min;
		for(j=0;j<n;j++)
			if(used[j]==0&&d[j]>distance[tag][j])
				d[j]=distance[tag][j];
	}
	printf("%d\n",sum);
}

• Re:人生的第一次交一遍就过的题 (4) wslgb2006 2010-03-05 12:48:05