| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
请问为什么会WA啊,#include<stdio.h>
#include<math.h>
#define inf 1e250
double dis[1005][1005];
typedef struct point
{
double x,y;
}point;
double distance(point p1,point p2)
{
point p;
p.x=p2.x-p1.x;
p.y=p2.y-p1.y;
return sqrt(p.x*p.x+p.y*p.y);
}
double prim(int n)
{
int i,j;
double list[1005],mindis,len;
int s[1005],k;
for(i=2;i<=n;i++)
{
list[i]=dis[1][i];
s[i]=0;
}
s[1]=1;
len=0.0;
for(i=2;i<=n;i++)
{
mindis=inf;
for(j=1;j<=n;j++)
{
if(s[j]==0 && list[j]<mindis)
{
k=j;
mindis=list[j];
}
}
s[k]=1;
len+=mindis;
for(j=1;j<=n;j++)
{
if(s[j]==0 && list[j]>dis[j][k])
list[j]=dis[j][k];
}
}
return len;
}
int main()
{
freopen("in.txt","r",stdin);
int i,j,n,m,tempi,tempj;
point p[1005];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
for(j=1;j<=i-1;j++)
dis[i][j]=dis[j][i]=distance(p[i],p[j]);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&tempi,&tempj);
dis[tempi][tempj]=dis[tempi][tempj]=0;
}
printf("%.2lf\n",prim(n));
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator