HDU 1245 Saving James Bond-白红宇

HDU 1245 Saving James Bond

阅读量：6757 次

发布时间：2019-06-26

本文共 1818 字，大约阅读时间需要 6 分钟。

计算几何+SPFA

我已经不想看我的提交记录了。。。。

HDU 我起码WA了2页。。。。

都是浮点数惹的祸。

const double eps=1e-4;abs(a-b)<=eps;

这样来推断相等。

总共 n 条鳄鱼，最多有 n*(n+1)/2 条路。

抽象化处理。

把中心的起点当作起点0 ；最多有 n+1 条路。

把鳄鱼和周围的边界的终点都当作 n+1 ; 最多有 n+1 条

总共就仅仅存在 n+2个点。

就是计算0 和 n+1 的最短距离。

有个小优化，就是当跳跃距离可以直接跳到岸上的时候就直接输出 42.5 1；

G++ ,C++ 都过了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              using namespace std;const double INF= 0xfffffff;bool vis[103];double dis[103];int path[103];int n;double m;const double eps=1e-4;struct lx{ int v; double len;};vector
              
               g[103];struct node{ double x,y;} point[101];void build(){ int u,v; for(int i=1; i<=n; i++) { double x=point[i].x; double y=point[i].y; double len; u=i; double xx,yy; lx now; xx=min(50.00-x,50.00-y); yy=min(50.00+x,50.00+y); len=min(xx,yy); if(len<=m) { now.v=n+1,now.len=len; g[u].push_back(now); } len=sqrt(x*x+y*y); if(len-7.5<=m) { now.len=len-7.5; now.v=u; g[0].push_back(now); } for(int j=i+1; j<=n; j++) { len=sqrt((x-point[j].x)*(x-point[j].x)+(y-point[j].y)*(y-point[j].y)); if(len<=m) { now.len=len; now.v=j; g[u].push_back(now); now.v=u; g[j].push_back(now); } } }}void SPFA(){ for(int i=0; i<103; i++) dis[i]=INF,vis[i]=0,path[i]=INF; queue
               
                q; dis[0]=0,vis[0]=1; q.push(0);path[0]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int j=0; j
                
                 path[u]+1) path[v]=path[u]+1; } else if(dis[v]>=dis[u]+len) { dis[v]=dis[u]+len; path[v]=path[u]+1; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(abs(dis[n+1]-INF)<=eps) puts("can't be saved"); else printf("%.2f %d\n",dis[n+1],path[n+1]);}int main(){ while(cin>>n>>m) { for(int i=0; i<103; i++) g[i].clear(); for(int i=1; i<=n; i++) scanf("%lf%lf",&point[i].x,&point[i].y); if(m>=42.50) { puts("42.50 1"); continue; } build(); SPFA(); }}