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<
