记录编号	31793	评测结果	AAAAAAAAAA
题目名称	129.[USACO Mar08] 麻烦的干草打包机	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2011-11-03 21:33:48	内存使用	4.94 MiB

#include<math.h>
#include<stdio.h>
#include<stdlib.h>

FILE *fi=fopen("baler.in","r");
FILE *fo=fopen("baler.out","w");

struct aaa
{
	double x,y,r,v;
}a[1100];
	
int n,s,v[1100][1100],t[1100];

bool b[1100];

double x,y,ans;

void dfs(int k)
{
	int i;
	if(a[k].x==x&&a[k].y==y)
	{
		fprintf(fo,"%.0lf\n",ans);
		fclose(fi);
		fclose(fo);
		exit(0);
	}
	for(i=1;i<=t[k];i++)
	{
		if(!b[v[k][i]])
		{
			a[v[k][i]].v=a[k].v*a[k].r/a[v[k][i]].r;
			ans+=a[v[k][i]].v;
			b[v[k][i]]=true;
			dfs(v[k][i]);
			b[v[k][i]]=false;
			ans-=a[v[k][i]].v;
		}
	}
}

int main()
{
	int i,j;
	fscanf(fi,"%d%lf%lf",&n,&x,&y);
	for(i=1;i<=n;i++)
	{
		fscanf(fi,"%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
		if(a[i].x==0&&a[i].y==0)
			s=i;
	}
	for(i=1;i<n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)==(a[i].r+a[j].r)*(a[i].r+a[j].r))
			{
				t[i]++;
				v[i][t[i]]=j;
				t[j]++;
				v[j][t[j]]=i;
			}
		}
	}
	a[s].v=10000;
	ans=10000;
	b[s]=true;
	dfs(s);
	return 0;
}