水题:还是wa了三次。主要问题是行数是n*(n-1)/2,刚开始没有审题,其次直接把结果存储在n里头,导致城市数目发生了改变
#include<stdio.h>
const int MAXN=500;
const int INF=0x7fffffff;
int map[MAXN][MAXN];
int dist[MAXN];
int pre[MAXN];
int n,ans;
void Prim()
{
int i,j,k;
int min;
bool p[MAXN];
for(i=2;i<=n;i++)
{
p[i]=false;
dist[i]=map[1][i];
pre[i]=1;
}
dist[1]=0;
p[1]=true;
for(i=1;i<=n-1;i++)
{
min=INF;
k=0;
for(j=1;j<=n;j++)
{
if(!p[j] && dist[j]<min)
{
min=dist[j];
k=j;
}
}
if(k==0) return ;
p[k]=true;
ans+=dist[k];
for(j=1;j<=n;j++)
{
if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
{
dist[j]=map[k][j];
pre[j]=k;
}
}
}
}
int main()
{
int i,j;
int a,b,c;
while(scanf("%d",&n) && n)
{
ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) map[i][j]=0;
else map[i][j]=INF;
}
int t=n*(n-1)/2;
for(i=0;i<t;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c) map[a][b]=map[b][a]=c;
}
Prim();
printf("%d\n",ans);
}
return 0;
}