记录编号	175369	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 麻烦的干草打包机	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.177 s
提交时间	2015-08-05 16:04:52	内存使用	8.96 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<cstring>
using namespace std;
struct dd
{
	int x,y,r;
	double su;
}jie[1500];
struct dr
{
	int zhong;
	int next;
}jiege[3500];
int tot;
double diss[1060];
int id,fg;
int n,begin,end,head[1060];
double dis[1060][1060];
bool v[1060];
double Sqrt(int i,int j)
{
	return sqrt((jie[i].x-jie[j].x)*(jie[i].x-jie[j].x)+(jie[i].y-jie[j].y)*(jie[i].y-jie[j].y));
}
void add(int x,int y)
{
	tot++;
	jiege[tot].zhong=y;
	jiege[tot].next=head[x];
	head[x]=tot;
}
void spfa(int y)
{
	v[y]=1;
	diss[y]=10000.0;
	queue<int>q;
	q.push(y);
	while(!q.empty())
	{   
		int yu=q.front();
		q.pop();
		v[yu]=0;
		for(int i=head[yu];i;i=jiege[i].next)
		{   int jk=jiege[i].zhong;
			if(!v[jk])
			{
				v[jk]=1;
				jie[jk].su=jie[yu].su*jie[yu].r/jie[jk].r;
				diss[jk]=diss[yu]+jie[jk].su;
				if(id==jk){
					printf("%.0lf",diss[jk]);
					return;
				}
				q.push(jk);
			}
		}
	}
}
int main()
{   freopen("baler.in","r",stdin);
    freopen("baler.out","w",stdout);
    scanf("%d%d%d",&n,&begin,&end);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&jie[i].x,&jie[i].y,&jie[i].r);
		if(jie[i].x==begin&&jie[i].y==end)
		  id=i;
		if(jie[i].x==0&&jie[i].y==0)
		  fg=i;
	}
	jie[fg].su=10000.0;
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=n;++j)
	 {
      if(i==j) continue;
      if(Sqrt(i,j)<=(jie[j].r+jie[i].r))
          add(i,j);
     }
	spfa(fg);
	return 0;
}