[SPFA+精度控制]hdoj 1245：Saving James Bond

大致题意：
? ? 给出一个100*100的池塘，池塘中心位于二维坐标原点。池塘中心有一个直径为15的圆形岛屿，一个人站在岛屿上。给出池塘中n个小岛的位置和这个人的最大步长。求这个人想到池塘对岸的话最少要走多长的距离，最少要迈多少步。

?

大致思路：
? ? 把小岛抽象为起点，对岸抽象为终点，求最短路即可。最短路的思路很好想到，但是需要精度控制的经验啊。

?

?

#include<iostream>#include<cmath>#include<cstdio>#include<fstream>#include<cstring>using namespace std;const int nMax=100050;const int mMax=1000050;const int inf=1<<30;const double eps=1e-12;struct{    int v, next;    double  w;}edge[mMax];int n,k,edgeHead[nMax];double dis[nMax];int stack[nMax],m;bool vis[nMax];int steps[nMax];void addedge(int a,int b,double w){    edge[k].w = w;    edge[k].v=b;    edge[k].next=edgeHead[a];    edgeHead[a]=k;k++;}int spfa(int s){    int i, top = 0;    memset(vis,0,sizeof(vis));    for(i=1;i<=n;i++){        dis[i]=inf;        steps[i]=inf;    }    dis[s]=steps[s]=0;    stack[++top]=s;    vis[s]=true;    while(top){        int u=stack[top--];        vis[u]=false; /////////////////        for(i=edgeHead[u];i!=0;i=edge[i].next){            int v=edge[i].v;            if(abs(dis[v]-(dis[u]+edge[i].w))<=eps){                if(steps[v]>steps[u]+1){                    steps[v]=steps[u]+1;                    if(!vis[v]){                        vis[v]=true;                        stack[++top]=v;                    }                }                continue;            }            if(dis[v]>dis[u]+edge[i].w){                dis[v]=dis[u]+edge[i].w;                steps[v]=steps[u]+1;                if(!vis[v]){                    vis[v]=true;                    stack[++top] = v;                }            }        }    }    int sum=0;    for(i=1;i<=n;i++){        sum+=dis[i];    }    return sum;}class fuck{    public:    int x,y;}node[nMax];int len;double getdis(int a,int b){    return sqrt((node[a].x-node[b].x)*(node[a].x-node[b].x)+(node[a].y-node[b].y)*(node[a].y-node[b].y));}int main(){    int i,j,s,t;    double d,e;    node[0].x=node[0].y=0;  //  freopen("gift.in","r",stdin);    while(scanf("%d%d",&n,&len)!=EOF){        k=1;        memset(edgeHead,0,sizeof(edgeHead));        for(i=1;i<=n;i++){            scanf("%d%d",&node[i].x,&node[i].y);        }        for(i=1;i<=n;i++){            for(j=1;j<=n;j++){                if(i==j)continue;                d=getdis(i,j);            //    cout<<d<<endl;                if(d<=len){                    addedge(i,j,d);                }            }        }        s=n+1;        t=n+2;        for(i=1;i<=n;i++){            d=getdis(0,i)-7.5;            if(d<=len){                addedge(s,i,d);            }            d=min(50-node[i].x,50-node[i].y);            e=min(node[i].x+50,node[i].y+50);            d=min(d,e);            if(d<=len){                addedge(i,t,d);            }        }        n+=2;        spfa(s);        if(fabs(dis[t]-inf)<=eps){            printf("can't be saved\n");            continue;        }        printf("%.2f %d\n",dis[t],steps[t]);    }    return 0;}