记录编号	79251	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 麻烦的干草打包机	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2013-11-05 11:23:47	内存使用	0.34 MiB

#include <fstream>
#include <deque>
#include <cmath>
using namespace std;
ifstream fi("baler.in");
ofstream fo("baler.out");
class T
{
public:
	int x,y,r,num;
};
T lun[1051];
int xt,yt,n,root,fu[1051],son;
bool f[1051];
double zs[1051];
deque <T> v;
void init()
{
	int i;
	fi>>n>>xt>>yt;
	for (i=1;i<=n;i++)
	{
		fi>>lun[i].x>>lun[i].y>>lun[i].r;
		lun[i].num=i;
	}
	for (i=1;i<=n;i++) {f[i]=true;zs[i]=0;}
	for (i=1;i<=n;i++)
	{
		if (lun[i].x==0&&lun[i].y==0) root=i;
		if (lun[i].x==xt&&lun[i].y==yt) son=i;
	}
	fu[root]=root;zs[root]=double(10000);
}
void bfs()
{
	int p,i;
	double lpr,lir,a2,b2;
	f[root]=false;
	v.push_back(lun[root]);
	while (v.size()!=0)
	{
		p=v[0].num;
		v.pop_front();
		for (i=1;i<=n;i++)
			if (f[i])
			{
				lpr=double(lun[p].r);lir=double(lun[i].r);
				a2=double(abs(lun[p].x-lun[i].x))*double(abs(lun[p].x-lun[i].x));
				b2=double(abs(lun[p].y-lun[i].y))*double(abs(lun[p].y-lun[i].y));
				if (abs(lpr+lir-sqrt(a2+b2))<0.00001)
				{
					f[i]=false;fu[i]=p;
					zs[i]=zs[p]*double(double(lun[p].r)/double(lun[i].r));
					v.push_back(lun[i]);
				}
			}
	}
}
int suan()
{
	int p=son;
	double ans=double(0);
	while (fu[p]!=p)
	{
		ans+=zs[p];
		p=fu[p];
	}
	return ans+10000;
}
int main()
{
	init();
	bfs();
	fo<<suan()<<endl;
	return 0;
}