这道题被坑的难受,很基础的题目,但是还是wa的郁闷,主要的错误是不懂的分析,导致变量的定义出错,记录k点的最短边要double的却依旧写int导致wa的找不出错了
#include<stdio.h>
#include<math.h>
#include<string.h>
const int MAXN=1100;
const int INF=0x7fffffff;
struct Node
{
int x,y;
} node[MAXN*2];
double map[MAXN][MAXN];
int n,flag;
double ans;
int pre[MAXN];
double dist[MAXN];
double _dist(Node a,Node b)
{
return sqrt((1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
void Prim()
{
int i,j,k;
double mn;
bool p[MAXN];
for(i=1; i<=n; i++)
{
p[i]=false;
dist[i]=map[1][i];
pre[i]=1;
}
p[1]=true;
ans=0;
for(i=1; i<=n-1; i++)
{
mn=INF;
k=0;
for(j=1; j<=n; j++)
{
if(!p[j] && dist[j]<mn)
{
mn=dist[j];
k=j;
}
}
p[k]=true;
ans+=dist[k];
if(k==0)
{
flag=1;
return ;
}
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 T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d%d",&node[i].x,&node[i].y);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
map[i][j]=_dist(node[i],node[j]);
if(map[i][j]>1000 || map[i][j]<10) map[i][j]=INF;
if(i==j) map[i][j]=0;
}
}
ans=flag=0;
Prim();
if(flag) printf("oh!\n");
else printf("%.1lf\n",ans*100.0);
}
return 0;
}