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