HDU 3681 Prison Break floyd+状压+二分

题目链接：点击打开链接

题意：

给定n*m的矩阵：

F：起点（有且仅有一个）

D:坏点（不能走到这个点）

G:能量池（走到这个点可以选择使用这个点的能量池，把电池充满，也可以暂时不用，只能使用一次）

Y:目标点

问：

遍历所有Y点需要最小的电池容量是多少。

开始电池满电，每走一步消耗一格电。

Y+G的个数<=15. n,m<=15

思路：状压YG，前面几位表示Y，后面几位表示G。

先跑个floyd，然后二分电池容量，状压dp判可行

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int inf = 5500; const int N = 15; struct node{ int x, y; node(int a=0, int b=0):x(a),y(b){} }Y[N], G[N], P[N+1], F; int ynum, gnum, dp[1<
        
          qx, qy; qx.push(x); qy.push(y); while(!qx.empty()){ int ux = qx.front(); qx.pop(); int uy = qy.front(); qy.pop(); for(int i = 0; i < 4; i++) { int vx = step[i][0] + ux, vy = step[i][1] + uy; if(false == (0<=vx && vx 
         
           State, End; for(int i = 0; i < ynum; i++) if(power - dis[F.x][F.y][Y[i].x][Y[i].y] >= 0) { dp[1<
          
           = 0) { dp[1<<(i+ynum)][i+ynum] = power; State.push(1<<(i+ynum)); End.push(i+ynum); } while(!State.empty()) { int s = State.front(); State.pop(); int e = End.front(); End.pop(); if((s & ((1<
           
            = ((1<
            
             >n>>m, n+m){ input(); if(ynum == 0){puts("0");continue;} floyd(); int ans = inf, l = 0, r = inf; while(l <= r){ int mid = (l+r)>>1; if(ok(mid)) r = mid-1, ans = min(ans, mid); else l = mid+1; } if(ans == inf) ans = -1; cout<