题目链接：点击打开链接
题目大意：在一个 100*100 坐标 以及 中心原点（起点）在（0，0）位置并且半径为 7.5 的圆形上，附近有很多的鳄鱼（可以跳到上面去），问是否可以跳到坐标外（包含边界），若可以，筛选出距离最短的路径（边长度为1），如果最短路径一样，筛选出第一跳实际跳的距离最短的那条路径，题目保证唯一。
解题思路：第一跳需要特殊处理，是否可以跳出成功，若可以则输出；否则开始建网，无脑上 Dijsktra，只是比经典的 Dijsktra 多了个第一跳的距离 fst[i] 的一个传递性。
AC 代码
usingnamespacestd; typedeflonglongll; constintmaxn=320; // 100 + 100*2（边界点：x，y分别一个）+ 1（原点）structnode{ intx,y; }nds[maxn]; intn,len; doubleD; intvis[maxn], dis[maxn], pre[maxn], fst[maxn]; intg[maxn][maxn]; voidinit() { mem(g,INF), mem(vis,0), mem(dis,INF), mem(pre,-1), mem(fst,INF); } doublefdis(nodea, nodeb) { returnsqrt(pow(a.x-b.x,2) +pow(a.y-b.y,2)); } voiddijkstra(ints) { dis[s]=0; while(1) { intmi=INF; s=-1; for(inti=0;i<len;i++) if(!vis[i] &&mi>dis[i]) mi=dis[i], s=i; if(s==-1) return; vis[s]=1; for(inti=0;i<len;i++) if(!vis[i] &&mi+g[s][i]<dis[i]) { dis[i]=mi+g[s][i], pre[i]=s; if(s!=0) fst[i]=fst[s]; // 传递第一跳的距离 } elseif(!vis[i] &&mi+g[s][i]==dis[i] &&fst[i]>fst[s]) // 路径距离相同时，较第一跳距离比较短的优先pre[i]=s, fst[i]=fst[s]; } } intmain() { scanf("%d%lf",&n,&D); n++; // 原点也算为一个点nds[0].y=nds[0].x=0; for(inti=1;i<n;i++) scanf("%d%d",&nds[i].x,&nds[i].y); if(D+7.5>=50) // 特判 { puts("1"); return0; } len=n; for(inti=1;i<n;i++) // 加入符合D的边界（河岸）的点if(50-abs(nds[i].x)<=D) nds[len].x=nds[i].x>=0?50:-50, nds[len++].y=nds[i].y; elseif(50-abs(nds[i].y)<=D) nds[len].y=nds[i].y>=0?50:-50, nds[len++].x=nds[i].x; init(); doublediff; for(inti=1;i<len;i++) { if((diff=fdis(nds[0],nds[i])-7.5)<=D) // 筛选原点到第一跳的距离g[i][0]=g[0][i]=1, fst[i]=diff; // 算出第一跳的距离// 除了原点，第二跳开始各自符合D的建边// why 原点到边界的不用算？ 因为上面有了特判for(intj=1;j<len;j++) if(i!=j&&fdis(nds[i],nds[j])<=D) g[i][j]=g[j][i]=1; } dijkstra(0); intmi=INF, h=-1; for(inti=n;i<len;i++) // 筛选第一优先级最小dis，第二优先级最小fstif(mi>dis[i] ||mi==dis[i] &&h!=-1&&fst[h]>fst[i]) mi=dis[i], h=i; if(mi!=INF) { printf("%d\n",mi); vector<int>vec; while(h!=-1) { vec.push_back(h); h=pre[h]; } for(inti=vec.size()-2;i>0;i--) // 原点和边界点无需输出printf("%d %d\n",nds[vec[i]].x,nds[vec[i]].y); } elseputs("0"); return0; }
