本文共 992 字，大约阅读时间需要 3 分钟。
题目方法：二分加bfs
题意：给你一个炸弹x，然后给你n个炸弹的位置，其中只能远程控制第一个炸弹爆炸，炸弹有一个爆炸范围，在此范围内，他可以引爆其他炸弹，现在想引爆炸弹x，问你炸弹的范围最小是多少
思路：其实这个题思路清晰一点就很容易想出来了，我们可以这样想，想引爆炸弹x，那么最大的爆炸范围就是1到x的距离，然后这是在一个二维坐标中，距离的大小我们只能使用二分查找，同时每一个炸弹在爆炸范围内可以引爆一定数量的炸弹，这样就成了一个bfs
一开始我一直时间超限，也不知道错在哪里，后来把写的方式改了一下，代码如下：
#include #include #include #include #include #include using namespace std;const int MAXN=550;const double ITF=0.001;struct Point{ int idx; double x,y; double d;} poin[MAXN];Point pp;int n;int vis[MAXN];int add[MAXN];double dis[MAXN][MAXN];double dig(int a,int b){ double temp=sqrt((poin[a].x-poin[b].x)*(poin[a].x-poin[b].x)+(poin[a].y-poin[b].y)*(poin[a].y-poin[b].y)); return temp;}bool bfs(double d){ memset(vis,0,sizeof(vis)); queue p; p.push(1); vis[1]=1; int cnt=0; while(!p.empty()) { cnt++; int t=p.front(); p.pop(); if(dis[t][n]<=d) { return true; } for(int i=2; i l+0.001) { mid=l+(r-l)/2; if(bfs(mid)) { r=mid; } else l=mid; } printf("%.2lf\n",r); } return 0;}
转载地址：http://sygsi.baihongyu.com/