题意：有一个三维的地图，有n个人被困住，现在消防队员只能从1楼的一个入口进入，营救被困者，每一个被困者有一个价值，当消防队员找到一个被困者之后，他可以营救或者见死不救，如果救的话，他必须马上将其背到入口处，不得停下，不得同时救多个人，而且回去的时间一步要做两步走，即时间增加一倍。求在给定时间S内，能救到的人的最大价值总和。
解法：bfs一遍记录每个点离起点的最短距离，那么救这个人的花费就是3*dis，然后已经知道救这个人的价值，那么最后求一个01背包即可。
要注意一个人都救不到的地方，我开始将dis都初始化为1000000007,这样的话如果走不到的话，花费就变成3*dis爆int了。悲剧。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#define Mod 10000007
using namespace std;
#define N 50107 char mp[][][];
int dis[][][];
int dp[];
int T[],P[],L,H,W;
int dx[] = {,,,, , -};
int dy[] = {,,-,, , ,};
int dz[] = {,,,-, , ,};
struct node {
int l,h,w,sec;
node(int _x,int _y,int _z,int _sec):l(_x),h(_y),w(_z),sec(_sec){}
node(){}
}vol[],S; bool OK(int x,int y,int z) {
if(x >= && x < L && y >= && y < H && z >= && z < W)
return true;
return false;
} void bfs(node S) {
queue<node> q;
while(!q.empty()) q.pop();
int i,j,k;
for(i=;i<L;i++)
for(j=;j<H;j++)
for(k=;k<W;k++)
dis[i][j][k] = Mod;
int x = S.l, y = S.h, z = S.w;
dis[x][y][z] = ;
q.push(S);
while(!q.empty()) {
node now = q.front();
q.pop();
int l = now.l, h = now.h, w = now.w, sec = now.sec;
if(mp[l][h][w] == 'U') {
for(k=;k<;k++) {
int nx = l + dx[k];
int ny = h + dy[k];
int nz = w + dz[k];
if(!OK(nx,ny,nz)) continue;
if(mp[nx][ny][nz] != 'X') {
if(sec+ < dis[nx][ny][nz]) {
dis[nx][ny][nz] = sec+;
node tmp = node(nx,ny,nz,sec+);
q.push(tmp);
}
}
}
}
else if(mp[l][h][w] == 'D') {
for(k=;k<;k++) {
if(k == ) continue;
int nx = l + dx[k];
int ny = h + dy[k];
int nz = w + dz[k];
if(!OK(nx,ny,nz)) continue;
if(mp[nx][ny][nz] != 'X') {
if(sec+ < dis[nx][ny][nz]) {
dis[nx][ny][nz] = sec+;
node tmp = node(nx,ny,nz,sec+);
q.push(tmp);
}
}
}
}
else {
for(k=;k<;k++) {
int nx = l + dx[k];
int ny = h + dy[k];
int nz = w + dz[k];
if(!OK(nx,ny,nz)) continue;
if(mp[nx][ny][nz] != 'X') {
if(sec+ < dis[nx][ny][nz]) {
dis[nx][ny][nz] = sec+;
node tmp = node(nx,ny,nz,sec+);
q.push(tmp);
}
}
}
}
}
} int main()
{
int t,n,STime,i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d",&L,&H,&W,&n,&STime);
for(i=;i<L;i++) {
for(j=;j<H;j++) {
scanf("%s",mp[i][j]);
for(k=;k<W;k++)
if(mp[i][j][k] == 'S')
S = node(i,j,k,);
}
}
for(i=;i<=n;i++)
{
scanf("%d%d%d%d",&vol[i].l,&vol[i].h,&vol[i].w,&P[i]);
vol[i].l--,vol[i].h--,vol[i].w--;
}
bfs(S);
for(i=;i<=n;i++)
T[i] = *dis[vol[i].l][vol[i].h][vol[i].w];
memset(dp,,sizeof(dp));
for(i=;i<=n;i++) {
for(j=STime;j>=;j--) {
if(j >= T[i])
dp[j] = max(dp[j],dp[j-T[i]]+P[i]);
}
}
int Maxi = ;
for(i=;i<=STime;i++)
Maxi = max(Maxi,dp[i]);
printf("%d\n",Maxi);
}
return ;
}