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 eterXroc at 2011-02-15 00:02:00 on Problem 3439
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>

long x[2000],y[2000],vis[2000],lt[2000][2],n,a,b;
//lt用来存广搜时的数据,lt[i][0]=k表示当前遍历到第k个点了,lt[i][1]存储从出发点到当前点的权值,vis[k]表示该点k是否已经遍历过
long map[2000][2000];

double dis(long x1,long x2,long y1,long y2)
{
       double tmp=sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
       return tmp;
}

int main()
{
    long t;
    scanf("%ld",&t);
    
    while(t--)
    {
        scanf("%ld%ld%ld",&n,&a,&b);
        
        double l1,l2,l;
        scanf("%lf%lf",&l1,&l2);
        
        l=l1+l2;
        
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        
        for(long i=1;i<=n;i++)
             scanf("%ld%ld",&x[i],&y[i]);
        
        for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
           {
               if(i==j) continue;
               double d=dis(x[i],x[j],y[i],y[j]);
               if(d-l<1e-8) 
               {
                    map[i][j]=1;
                    map[j][i]=1;
               }
           }
        
        long i=0,j=1;
        lt[0][0]=a;
        lt[0][1]=0;
        vis[a]=1;//起点a,终点b
        
        while(i<j)
        {
             long ns=lt[i][0];    
             if(map[ns][b]) {vis[b]=1;printf("%ld\n",lt[i][1]+1);break;}
             for(long k=1;k<=n;k++)
             {     
                if(map[ns][k]&&!vis[k])
                {
                     lt[j][0]=k;
                     lt[j][1]=lt[i][1]+1;
                     vis[k]=1;
                     j++;
                }
             }
             i++;
        }
                     
        if(!vis[b]) printf("Impossible\n");
        
    }
  //  system("PAUSE");
}

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