#include<stdio.h>
#define MAXN 1008
int data[MAXN][MAXN];
int min[MAXN],v[MAXN];
int prim(int n){
	int ans=0;
	int i,j,k,mx;
	for(i=1;i<=n;i++){
	   min[i]=data[1][i];
	   v[i]=0;
	}
	v[1]=1;
	for(j=1;j<=n-1;j++){
		mx=1000008;
		for(i=1;i<=n;i++)
			if(!v[i]&&min[i]<mx) {k=i;mx=min[i];}
		v[k]=1;
		ans+=min[k];
		if(k==n) 	return ans;
		for(i=1;i<=n;i++)
			if(!v[i]&&data[k][i]<min[i]) min[i]=data[k][i];
	}
}
int main()
{
	int i,j,t,n;
	int x,y,z;
	while(scanf("%d%d",&t,&n)!=EOF){
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
               data[i][j]=1000008;
		for(i=1;i<=t;i++){
			  scanf("%d%d%d",&x,&y,&z);
			  if(z<data[x][y]){
			     data[x][y]=z;
			     data[y][x]=z;
              }
        }
		printf("%d\n",prim(n));
	}
	return 0;
}



#include<stdio.h>
#define MAXN 1008
int data[MAXN][MAXN];
int min[MAXN],v[MAXN];
void Dijstala(int n)
{
	int i,j,k,mx;
	for(i=1;i<=n;i++){
	   min[i]=data[1][i];
	   v[i]=0;
	}
	v[1]=1;
	for(j=1;j<=n-1;j++){
		mx=1000008;
		for(i=1;i<=n;i++)
			if(!v[i]&&min[i]<mx) {k=i;mx=min[i];}
		v[k]=1;
		for(i=1;i<=n;i++)
			if(!v[i]&&min[k]+data[k][i]<min[i]) 
                 min[i]=data[k][i]+min[k];
	}
}
int main()
{
	int i,j,t,n;
	int x,y,z;
	while(scanf("%d%d",&t,&n)!=EOF){
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
               data[i][j]=1000008;
		for(i=1;i<=t;i++){
			  scanf("%d%d%d",&x,&y,&z);
			  if(z<data[x][y]){
			     data[x][y]=z;
			     data[y][x]=z;
              }
        }
        Dijstala(n);
		printf("%d\n",min[n]);
	}
	return 0;
}

• Re:为什么用PRIM WA，而改一下代码用DIJSTALA就对了，附上代码求教！！！！！！！ (64) zjnu09220233 2010-10-27 14:55:00
  • Re:知道自己为什么错了，晕啊，两种算法还是有很大区别的！！！！！！！ (0) zjnu09220233 2010-10-27 15:05:02