记录编号	34512	评测结果	AWWWWWWWWW
题目名称	[USACO Mar08] 麻烦的干草打包机	最终得分	10
用户昵称	QhelDIV	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2011-12-17 14:06:00	内存使用	1.00 MiB

#include<fstream>
using namespace std;
ifstream fin("baler.in");
ofstream fout("baler.out");

int N,T_x,T_y,S_pos,T_pos,Total,Max;
int Map[1060][1060],Min=100000000;
bool bo=false;
class
{
public:
	int X,Y,S,D;
	double L;
}Gear[1060];

bool check(int p1,int p2)
{
int ox,oy;
	ox=Gear[p1].X-Gear[p2].X;
	ox=ox*ox;
	oy=Gear[p1].Y-Gear[p2].Y;
	oy=oy*oy;
	if(ox+oy==int((Gear[p1].L+Gear[p2].L)*(Gear[p1].L+Gear[p2].L)))
		return true;
	else
		return false;
}

void init()
{
int i,j;	
	fin>>N>>T_x>>T_y;
	
	for(i=1;i<=N;i++)
	{
		fin>>Gear[i].X>>Gear[i].Y>>Gear[i].L;
		if(Gear[i].X==0 && Gear[i].Y==0)
			S_pos=i;
		if(Gear[i].X==T_x && Gear[i].Y==T_y)
			T_pos=i;		
	}
	
	Gear[S_pos].S=10000;
	Gear[S_pos].D=1;
	
	for(i=1;i<=N;i++)
		for(j=i+1;j<=N;j++)
			if(check(i,j)==true)
			{
				Map[i][++Map[i][0]]=j;
				Map[j][++Map[j][0]]=i;
			}
	
	Total=10000;Max=Total;
}

void Ad_Hoc(int x)
{
int i,j;
	if(x==T_pos)
	{
		if(Min>Total)
			Min=Total;
	}
	if(bo==false)
	for(i=1;i<=Map[x][0];i++)
		if(Gear[Map[x][i]].S==0)
		{
			Gear[Map[x][i]].S=Gear[x].S*(Gear[x].L/Gear[Map[x][i]].L);
			Gear[Map[x][i]].S=0-Gear[Map[x][i]].S;
			
			Total=Total+((Gear[Map[x][i]].S>0)?Gear[Map[x][i]].S:(0-Gear[Map[x][i]].S));
			
			Ad_Hoc(Map[x][i]);
			Total=Total-((Gear[x].S>0)?Gear[x].S:(0-Gear[x].S));
		}
}

int main()
{
	init();
	
	Ad_Hoc(S_pos);
	fout<<Min<<endl;
	fin.close();
	fout.close();
}