hdu 1245 Saving James Bond

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <queue>
  5 #include <algorithm>
  6 #define maxn 500
  7 using namespace std;
  8 const double inf=99999999.0;
  9 
 10 int n,m;
 11 double d;
 12 double g[maxn][maxn];
 13 double dis[maxn];
 14 bool vis[maxn];
 15 int step[maxn*4];
 16 struct node
 17 {
 18    int x,y;
 19 }p[maxn];
 20 
 21 double min(double x,double y)
 22 {
 23     if(x>y) return y;
 24     return x;
 25 }
 26 
 27 double sqr(int x)
 28 {
 29     return x*x;
 30 }
 31 
 32 double dist(int x1,int y1,int x2,int y2)
 33 {
 34     return sqrt(sqr(x1-x2)+sqr(y1-y2));
 35 }
 36 
 37 
 38 void spfa()
 39 {
 40     queue<int>q;
 41     memset(vis,false,sizeof(vis));
 42     for(int i=0; i<=n+1; i++)
 43     {
 44         dis[i]=inf;
 45     }
 46     dis[0]=0.0;
 47     vis[0]=true;
 48     step[0]=0;
 49     q.push(0);
 50     while(!q.empty())
 51     {
 52         int u=q.front(); q.pop();
 53         vis[u]=false;
 54         for(int i=1; i<=n+1; i++)
 55         {
 56             if(g[u][i]<=d)
 57             {
 58                 if(g[u][i]+dis[u]<dis[i])
 59                 {
 60                     dis[i]=dis[u]+g[u][i];
 61                     step[i]=step[u]+1;
 62                     if(!vis[i])
 63                     {
 64                         vis[i]=true;
 65                         q.push(i);
 66                     }
 67                 }
 68                 else if(g[u][i]+dis[u]==dis[i])
 69                 {
 70                     if(step[i]>step[u]+1)
 71                     {
 72                         step[i]=step[u]+1;
 73                         if(!vis[i])
 74                         {
 75                             vis[i]=true;
 76                             q.push(i);
 77                         }
 78                     }
 79                 }
 80             }
 81         }
 82     }
 83 }
 84 int main()
 85 {
 86     while(scanf("%d%lf",&n,&d)!=EOF)
 87     {
 88         for(int i=1; i<=n; i++)
 89         {
 90             scanf("%d%d",&p[i].x,&p[i].y);
 91         }
 92         for(int i=1; i<=n; i++)
 93         {
 94             g[i][i]=0.0;
 95             for(int j=1; j<=n; j++)
 96             {
 97                 g[i][j]=dist(p[i].x,p[i].y,p[j].x,p[j].y);
 98             }
 99         }
100         g[0][0]=0.0;
101         for(int i=1; i<=n; i++)
102         {
103             g[i][0]=0.0;
104             g[0][i]=dist(0,0,p[i].x,p[i].y)-7.5;
105         }
106         for(int i=1; i<=n; i++)
107         {
108             g[n+1][i]=0.0;
109             g[i][n+1]=min(50.0-fabs((double)p[i].x),50.0-fabs((double)p[i].y));
110         }
111         g[0][n+1]=inf;
112         spfa();
113         if(dis[n+1]==inf)
114             printf("can‘t be saved\n");
115         else
116             printf("%.2lf %d\n",dis[n+1],step[n+1]);
117     }
118     return 0;
119 }