[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;
}