记录编号	79079	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 麻烦的干草打包机	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2013-11-05 06:55:07	内存使用	0.35 MiB

#include<fstream>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<deque>
using namespace std;
ifstream fi("baler.in");
ofstream fo("baler.out");
const int MAXN=1100;
int N,father[MAXN];
class Gear
{
public:
	double x,y,r,roll;
	bool boo;
}g[MAXN];
bool Connect(int j,int k){return (g[j].x-g[k].x)*(g[j].x-g[k].x)+(g[j].y-g[k].y)*(g[j].y-g[k].y)==(g[j].r+g[k].r)*(g[j].r+g[k].r);}
int main()
{
	int startG,endG;
	double X_t,Y_t;
	fi>>N>>X_t>>Y_t;
	for(int i=1;i<=N;i++)
	{
		fi>>g[i].x>>g[i].y>>g[i].r;
		g[i].boo=false;
		if(g[i].x==0&&g[i].y==0)startG=i;
		if(g[i].x==X_t&&g[i].y==Y_t)endG=i;
	}
	g[startG].roll=10000.0;
	//=========================================================
	memset(father,-1,sizeof(father));
	deque <int> q;
	q.push_back(startG);
	g[startG].boo=true;
	int tmp;
	while(!g[endG].boo)
	{
		tmp=q.front();
		q.pop_front();
		for(int i=1;i<=N;i++)
			if((!g[i].boo)&&Connect(tmp,i))
			{
				father[i]=tmp;
				g[i].roll=g[tmp].roll*g[tmp].r/g[i].r;
				g[i].boo=true;
				q.push_back(i);
			}
	}
	//==========================================================
	double ans=g[startG].roll;
	int j=endG;
	while(father[j]!=-1)
	{
		ans+=g[j].roll;
		j=father[j];
	}
	fo<<setiosflags(ios::fixed)<<setprecision(0)<<ans<<endl;
	return 0;
}