比赛 |
20111102 |
评测结果 |
AAAAAAAAAA |
题目名称 |
麻烦的干草打包机 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-02 19:36:28 |
显示代码纯文本
#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;
}
}