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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
double w[1060][3],q[1060][3],x0,y3;
int number,qi=0,mo=0,temp=-1;
bool used[1060]={0};
double absa(double  a);
void bfs(int x);
int main()
{
	freopen ("baler.in","r",stdin);
	freopen ("baler.out","w",stdout);
	scanf("%d",&number);
	cin>>x0>>y3;
	for (int i=0;i<number;i++)
	{
		cin>>w[i][0]>>w[i][1]>>w[i][2];
		if (w[i][0]==0&&w[i][1]==0)
		{
			q[0][0]=i;
			q[0][1]=-1;
			q[0][2]=10000;
			used[i]=1;
		}
	}
	while (qi<=mo)
	{
		bfs(qi);
		if (temp!=-1)
		{
			break;
		}
		qi++;
	}
	double answer=0;
	while (temp!=-1)
	{
		answer+=q[temp][2];
		temp=q[temp][1];
	}
	printf("%.lf",answer);
	return 0;
}
void bfs(int x)
{
	if (w[(int)q[x][0]][0]==x0&&w[(int)q[x][0]][1]==y3)
	{
		temp=x;
		return;
	}
	else
	{
		for (int i=0;i<number;i++)
		{
			if (used[i])
			{
				continue;
			}
			else
			{
				if ((absa(w[i][0]-w[(int)q[x][0]][0])*absa(w[i][0]-w[(int)q[x][0]][0])+absa(w[i][1]-w[(int)q[x][0]][1])*absa(w[i][1]-w[(int)q[x][0]][1]))==((w[i][2]+w[(int)q[x][0]][2])*(w[i][2]+w[(int)q[x][0]][2])))
				{
					mo++;
					used[i]=1;
					q[mo][0]=i;
					q[mo][1]=x;
					q[mo][2]=(q[x][2]*w[(int)q[x][0]][2])/w[i][2];
				}
			}
		}
	}
}
double absa(double  a)
{
	if (a>=0)
	{
		return a;
	}
	else
	{
		return -a;
	}
}