HDU_1245
这个题目首先要遍历一遍所有的点，将第一次可以到达的点加入到SPFA的队列之中，并设定相应的d[]及step[]的值，其余的d[i]和step[i]都初始化成INF，之后便求出到各个点的最短路以及最短的步数，最后再扫描一遍所有点，把可以跳出lake的点做进一步的处理即可。
#include<stdio.h>
#include<string.h>
#include<math.h>
double d[110],D,x[110],y[110];
int step[110],q[110],inq[110],reach[110];
double dis(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
int i,j,k,n,N,u,v,ans_s,front,rear;
double temp,ans_d;
while(scanf("%d%lf",&n,&D)==2)
{
N=0;
for(i=0;i<n;i++)
{
scanf("%lf%lf",&x[N],&y[N]);
if(x[N]<50.0&&x[N]>-50.0&&y[N]<50.0&&y[N]>-50.0
&&sqrt(x[N]*x[N]+y[N]*y[N])>7.5-1e-7)
N++;
}
if(D+1e-7>42.5)
{
printf("42.50 1\n");
continue;
}
front=rear=0;
memset(inq,0,sizeof(inq));
for(i=0;i<N;i++)
{
temp=sqrt(x[i]*x[i]+y[i]*y[i])-7.5;
if(temp<D+1e-7)
{
d[i]=temp;
step[i]=1;
q[rear++]=i;
inq[i]=1;
}
else
{
d[i]=1000000001.0;
step[i]=1000000001;
}
}
while(front!=rear)
{
u=q[front++];
inq[u]=0;
if(front>N)
front=0;
for(v=0;v<N;v++)
if(u!=v&&dis(u,v)<D+1e-7)
{
temp=d[u]+dis(u,v);
if(temp<d[v]-1e-7)
{
d[v]=temp;
step[v]=step[u]+1;
if(!inq[v])
{
q[rear++]=v;
inq[v]=1;
if(rear>N)
rear=0;
}
}
if(fabs(temp-d[v])<1e-7&&step[u]+1<step[v])
{
step[v]=step[u]+1;
if(!inq[v])
{
q[rear++]=v;
inq[v]=1;
if(rear>N)
rear=0;
}
}
}
}
memset(reach,0,sizeof(reach));
for(i=0;i<N;i++)
{
temp=fabs(x[i]+50.0);
if(fabs(x[i]-50.0)<temp)
temp=fabs(x[i]-50);
if(fabs(y[i]+50.0)<temp)
temp=fabs(y[i]+50);
if(fabs(y[i]-50)<temp)
temp=fabs(y[i]-50);
if(temp<D+1e-7)
reach[i]=1;
d[i]+=temp;
step[i]++;
}
ans_d=1000000001.0;
ans_s=1000000001;
for(i=0;i<N;i++)
if(reach[i])
{
if(d[i]<ans_d-1e-7)
{
ans_d=d[i];
ans_s=step[i];
}
if(fabs(d[i]-ans_d)<1e-7&&step[i]<ans_s)
ans_s=step[i];
}
if(ans_d<1000000000.0)
printf("%.2f %d\n",ans_d,ans_s);
else
printf("can't be saved\n");
}
return 0;
}