posted on 2021-05-03 20:50:49 | under 题解 | source
首先输入，记录一下哪个齿轮的位置在 \((0,0)\)，哪个在 \((x_t,y_t)\)。
接着，为了避免多次判断两个齿轮相切而超时，我们可以预处理一个 \(link_{i,j}\)，表示第 \(i\) 个齿轮是否和第 \(j\) 个齿轮相切。
这部分直接 \(O(n^2)\) 暴力即可，注意 \(link_{i,i}\) 要 \(=0\)，不然 bfs 时会重复搜自己。
怎么判断两个齿轮是否相切？我们小学二年级都学过一种距离，叫「欧几里得距离」。设两个点分别在 \((x_1,y_1)\) 和 \((x_2,y_2)\)，那它们的距离就是：
\[dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}
\]
怎么把它运用到这道题上呢？很简单，如果两个齿轮的圆心的距离等于这两个齿轮的半径之和，就说这两个齿轮相切。
实际运用时，为了防止被卡精度，一般对等式两边开平方，也就是：
\[(x_1-x_2)^2+(y_1-y_2)^2=(r_1+r_2)^2
\]
处理完 \(link_{i,j}\)，就可以直接暴力 bfs 了。
bfs 的结点记录三个东西：当前是哪一个齿轮，当前齿轮的速度，当前经过齿轮的总速度。
题目要求「绝对值之和」，那就忽视计算速度这个负号。
每次扩展结点时，要选没扩展过而且与它相切的齿轮。
这样的 bfs，每个结点只会搜一次，每个结点要遍历一次 \(1\) 到 \(n\)，时间复杂度为 \(O(n^2)\)。
最后输出答案要注意，直接向下取整，而不是四舍五入。
代码实现：
#include <queue>
#include <cstdio>
using namespace std;
int f(int a){return a*a;}//开平方函数，用 define 会计算很多次，不推荐
struct Roller{
int x,y,r;
Roller(int a=0,int b=0,int c=0):x(a),y(b),r(c){}
friend bool check(Roller a,Roller b){
return f(a.x-b.x)+f(a.y-b.y)<=f(a.r+b.r);//判断相切
}
friend bool operator==(Roller a,Roller b){
return a.x==b.x&&a.y==b.y;//判断相等
}
} a[1060];
int n,si,ei,ex,ey;
bool vis[1060],link[1060][1060];//vis 记录这个齿轮有没有被扩展过
struct Node{
int i;
double v,tot;//float 已死
Node(int a,double c,double d):i(a),v(c),tot(d){}
};
queue<Node> q;
int bfs(){
q.push(Node(si,10000.0,10000.0));
vis[si]=1;//搜索记得标记起点
while(!q.empty()){
Node now=q.front();q.pop();
if(now.i==ei) return (int)now.tot;//向下取整
for(int i=1;i<=n;i++){
if(!vis[i]&&link[now.i][i]){
vis[i]=1;
double v=now.v*(1.0*a[now.i].r/a[i].r);//计算扩展的齿轮的速度，注意 *1.0
q.push(Node(i,v,now.tot+v));
}
}
}
return -1;
}
int main(){
scanf("%d%d%d",&n,&ex,&ey);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
if(a[i]==Roller(0,0)) si=i;
if(a[i]==Roller(ex,ey)) ei=i;//记录头尾
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(check(a[i],a[j])) link[i][j]=link[j][i]=1;//预处理link[i][j]
}
}
printf("%d",bfs());
return 0;
}