| ||||||||||
| 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 <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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator