题目背景
![[luogu P3786]萃香抱西瓜 [spfa][状态压缩]](https://image.miaokee.com:8440/aHR0cHM6Ly9sdW9ndS5vc3MtY24taGFuZ3pob3UuYWxpeXVuY3MuY29tL3VwbG9hZC9waWMvNTU2NS5wbmc%3D.png?w=700&webp=1 "[luogu P3786]萃香抱西瓜 [spfa][状态压缩]")
伊吹萃香(Ibuki Suika)正在魔法之森漫步，突然，许多西瓜(Suika)从四周飞来，划出了绚丽的轨迹。虽然阵势有点恐怖，但她还是决定抱走一些西瓜。
题目描述
萃香所处的环境被简化为一个长为h，宽为w的网格平面。X坐标范围为[1,w]，y坐标范围为[1,h]。
她初始（第1个时刻）站在坐标为sx,sy的方格。
西瓜可能在任意一个方格出现，在每个时间单位，它们可能向任何一个方向移动，也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为n个，但只有m个西瓜可以被萃香抱走，因为其他都太大了，可能会砸伤她。
整个过程会持续T个时刻。萃香希望可以抱走全部的m个西瓜，并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻，与该西瓜处于同一位置。另外，由于萃香不愿耗费过多体力到处乱跑，她每个时刻可以选择静止不动，也可以选择移动到相邻的四个格子之一，只要不越出环境边界。如果选择移动到相邻格子，则算作移动了一次。(第1个时刻萃香刚站定，无法移动)
在每个时刻，如果萃香选择移动，可以认为萃香与西瓜同时从原来的位置移到了新的位置，没有先后顺序。
萃香想要知道，不被任何一个大西瓜砸中，并得到所有的m个小西瓜的情况下，最少需要移动多少次。
输入输出格式
输入格式：
第一行五个整数h,w,T,sx,sy，含义见题目描述。
第二行两个整数n,m，含义见题目描述。
接下来n段数据，每一段描述了一个西瓜的出现位置，时间，移动方式，是否可以被抱走等内容，具体如下:
首先一行，两个整数t1,t2，表示西瓜在t1时刻出现， t2时刻消失。若t2=T+1,表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。
接下来一行一个整数a,只能为0或1,0表示这个西瓜需要避开，1表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有m个。
接下来t2-t1行，每一行两个整数x,y，顺序描述了从t1时刻到t2-1时刻，该西瓜的坐标。西瓜的移动不一定是连续的，并且是一瞬间完成的，所以无需考虑萃香是否站在了移动路径上。
输出格式：
如果萃香在整个T时刻内无法避免被大西瓜砸中或者无法收集到所有m个小西瓜，输出-1,否则输出一个整数，表示萃香需要移动的最少次数。
输入输出样例
5 5 10 3 3
1 1
1 11
1
3 4
5 2
3 5
1 1
5 4
3 4
2 1
1 1
1 1
5 5
1
说明
样例说明:第2~4个时刻萃香站着不动，在第6个时刻，西瓜出现在萃香旁边，萃香移动到(3,4)位置即可抱走这个西瓜。
数据范围和提示:
子任务可能出现两种特殊性质A和B
A: 所有西瓜t1=1,t2=T+1
所有西瓜全程都静止在原地，不会发生移动。
B：m=0
共有10个子任务。
对于子任务1，具有特殊性质A和B
对于子任务2~3，仅具有特殊性质A
对于子任务4~5，仅具有特殊性质B
对于子任务6~10，不具有任何一个特殊性质。
对于全部子任务
1<=所有横坐标范围<=w
1<=所有纵坐标范围<=h
1<=h,w<=5
1<=T<=100
1<=t1<=T
2<=t2<=T+1
t1<t2
1<=n<=20
0<=m<=10
m<=n一个位置不会同时出现两个或以上西瓜。
有趣的状压spfa
以及一开始感到神秘的 !!i
偷一波orangebird的官方题解
**********************************************************
子任务1:所有西瓜始终出现且不动，并且没有要抱走的。
解法:只需要判断初始位置是否被大西瓜挡住，挡住输出-1，否则输出0即可
子任务2~3:所有西瓜始终出现且不动。
解法:由于要抱走的西瓜最多为10个，考虑用长度为10的0/1串来表示某个西瓜是否已经获取。状压spfa或dp即可解决。
子任务4~5:没有需要抱走的西瓜
解法:将时间看做一个维度，构建好三维的地图，把西瓜看做障碍，做三维的最短路或dp即可。
正解:
结合子任务2~3和4~5的做法，做一个四维的状压最短路或dp即可解决。
**********************************************************
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f inline int read(){
int re=;
bool flag=;
char ch;
while((ch=getchar())!='-'&&(ch<''||ch>''));
ch=='-'?flag=:re=ch-'';
while((ch=getchar())>=''&&ch<='') re=(re<<)+(re<<)+ch-'';
return flag?-re:re;
} struct node{
int nows,nowt,nowx,nowy;
node(int nows=,int nowt=,int nowx=,int nowy=):
nows(nows),nowt(nowt),nowx(nowx),nowy(nowy){}
}; const int maxm=,maxsize=,maxt=; int mp[maxsize][maxsize][maxt];
int dis[maxsize][maxsize][maxt][<<maxm];
bool vis[maxsize][maxsize][maxt][<<maxm];
const int dirx[]={,,-,,},diry[]={,,,,-};
const int stop=;
int mx,my,T,sx,sy;
int n,m,cnt=-;
queue<node> que; void init(){
memset(mp,inf,sizeof mp);
mx=read(); my=read(); T=read(); sx=read(); sy=read();
n=read(); m=read();
for(int i=;i<=n;i++){
int t1=read(),t2=read(),a=read();
if(!a) a=stop;
else a=++cnt;
for(int i=t1;i<t2;i++){
int x=read(),y=read();
mp[x][y][i]=a;
}
}
} void spfa(){
que.push(node(,,sx,sy));
memset(dis,inf,sizeof dis);
dis[sx][sy][][]=;
while(!que.empty()){
node now=que.front(); que.pop();
vis[now.nowx][now.nowy][now.nowt][now.nows]=;
if(now.nowt==T) continue;
for(int i=;i<;i++){
int nexx=now.nowx+dirx[i];
int nexy=now.nowy+diry[i];
int next=now.nowt+;
int nexs;
if(nexx<||nexx>mx||nexy<||nexy>my) continue;
if(mp[nexx][nexy][next]==stop) continue;
if(mp[nexx][nexy][next]==inf) nexs=now.nows;
else nexs=now.nows|(<<mp[nexx][nexy][next]);
if(dis[nexx][nexy][next][nexs]<=dis[now.nowx][now.nowy][now.nowt][now.nows]+!!i) continue;
dis[nexx][nexy][next][nexs]=dis[now.nowx][now.nowy][now.nowt][now.nows]+!!i;
if(!vis[nexx][nexy][next][nexs]){
vis[nexx][nexy][next][nexs]=;
que.push(node(nexs,next,nexx,nexy));
}
}
}
} void solve(){
spfa();
int ans=inf;
for(int i=;i<=mx;i++)
for(int j=;j<=my;j++)
ans=min(ans,dis[i][j][T][(<<m)-]);
if(ans==inf) ans=-;
printf("%d\n",ans);
} int main(){
//freopen("temp.in","r",stdin);
init();
if(mp[sx][sy][]==stop){
puts("-1");
return ;
}
solve();
return ;
}