洛谷 P2903

题目链接

分析

首先将齿轮抽象成点，齿轮的带动关系抽象成边。

由于 $n$ 很小所以我们可以暴力连边，如果两点之间的欧几里得距离小于两点的半径和，则连边。

连完边后从起点DFS 记录每个点的转速，和 $an{s}_i$ 表示以点 $i$ 结束的转速和，如果搜到了终点就返回，注意开 double。

代码

#include <bits/stdc++.h>
#define debug puts("Y")
#define inf 0x3f3f3f3f
#define int long long

using namespace std;

const int N = 100005;
int n, sx, sy, stid, etid, vis[N];
double sum, sp[N], ans[N];
vector <int> nbr[N];
struct node {
	double x, y, r;
}d[N];

double dist(double X1, double Y1, double X2, double Y2) {
	return sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2));
}
void dfs(int x) {
	if (x == etid) {
		return ;
	}
	vis[x] = true;
	for (int nxt : nbr[x]) {
		if (vis[nxt]) {
			continue;
		}
		sp[nxt] = sp[x] * d[x].r / d[nxt].r;
		ans[nxt] = ans[x] + sp[nxt];
		dfs(nxt);
	}
}

signed main() {
	cin >> n >> sx >> sy;
	for (int i = 1; i <= n; i ++) {
		cin >> d[i].x >> d[i].y >> d[i].r;
		if (d[i].x == 0 && d[i].y == 0) {//记录起点下标
			stid = i;
		} if (d[i].x == sx && d[i].y == sy) {//记录终点下标
			etid = i;
		} 
	} 
	for (int i = 1; i <= n; i ++) {
		for (int j = i + 1; j <= n; j ++) {
			if (d[i].r + d[j].r >= dist(d[i].x, d[i].y, d[j].x, d[j].y)) {
				nbr[i].push_back(j);
				nbr[j].push_back(i);
			}
		}
	}
	sp[stid] = ans[stid] = 10000;
	dfs(stid);
	cout << (int)(ans[etid]);//输出时强制转化为int
  return 0;
}