Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请问为什么会WA啊,

Posted by 264 at 2009-08-06 19:37:54 on Problem 3625
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator