自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:24:05，当前版本为作者最后更新于2022-11-06 19:02:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

和std不同。剪枝后的分层图最短路。

思路

点 $(o,i,j)$ 表示已经拿了 $o$ 个人，现在我位置在 $(i,j)$，还没计算 $(i,j)$ 位置的危险值，已经走过的路上的危险值之和。

酱紫转移：

• 不吃 $d_{ij}$，找一个包含 $(i,j)$ 的矩形 $[ax,bx,ay,by]$，即满足 $ax\leq i\leq bx,ay\leq j\leq by$，然后转移到 $(bx+1,k) | j\leq k\leq by$ 和 $(k,by+1) | i\leq k\leq bx$。
• 吃了 $d_{ij}$，转移到 $(i+1,j)$ 和 $(i,j+1)$。

剪枝

先来一个卡常小玩意：按 $o$ 从小到大进行转移，当前 $o$ 维护堆，$o+1$ 维护一个 vector，++o 时再用 vector 构建堆。

最关键的剪枝来喽：

根据 dij 的特殊性质，同一个 $o$ 的危险值是不降的。而通过矩形转移的时候不吃 $d$，也就是说在 $o$ 优的到 $o+1$ 也优。这是剪枝可行的前提。

那么对于每个矩形，记录一下已经更新过的 $(bx+1,k)$ 和 $(k,by+1)$，后面遇到更劣的时候就不更新了。我的做法是记了两个 $k$ 更新到的最小位置值。

复杂度分析

有 $nm(w+1)$ 个点。

有至多 $(n+m)k(w+1)$ 条边。

算上堆，复杂度 $\mathcal O(nmw+(n+m)kw\log(n+m)k)$。

code

#include<stdio.h>
#include<queue>
#include<string.h>
#define N 201
#define M 101
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node
{
	int i,j;long long ans;
	inline node(){}
	inline node(const int&a,const int&b,const long long&c)
		{i=a;j=b;ans=c;}
	inline bool operator<(const node&kkk)const{return ans>kkk.ans;}
};
int n,m,p,w,ax[N],bx[N],ay[N],by[N],ux[M][N],uy[M][N],a[N][N];
priority_queue<node>q;vector<node>qwq[M];
long long minn=1ll<<60,ans[M][N][N];
main()
{
	read(n);read(m);read(p);read(w);if(w>p)w=p;
	for(int i=0;i<n;++i)for(int j=0;j<m;read(a[i][j++]));
	for(int i=0;i<p;++i)
	{
		read(ax[i]);read(bx[i]);read(ay[i]);read(by[i]);
		--ax[i];--bx[i];--ay[i];--by[i];
		for(int j=0;j<=w;++j)ux[j][i]=bx[i],uy[j][i]=by[i];
	}
	memset(ans,0x3f,sizeof(ans));
	ans[0][0][0]=0;qwq[0].emplace_back(0,0,0);
	for(int o=0;o<=w;++o)
	{
		q=priority_queue<node>(qwq[o].begin(),qwq[o].end());
		for(node i;q.size();)
		{
			i=q.top();q.pop();
			if(minn<=i.ans)break;
			if(i.i+i.j>=n+m-1){minn=i.ans;break;}
			if(i.i==n||i.j==m)continue;
			if(o<w)for(int j=0;j<p;++j)if(ax[j]<=i.i&&i.i<=bx[j])
				if(ay[j]<=i.j&&i.j<=by[j])
			{
				for(int k=i.i;k<=ux[o][j];++k)
					if(ans[o+1][k][by[j]+1]>i.ans)
						qwq[o+1].emplace_back(k,by[j]+1,
							ans[o+1][k][by[j]+1]=i.ans);
				if(i.i<=ux[o][j])ux[o][j]=i.i-1;
				for(int k=i.j;k<=uy[o][j];++k)
					if(ans[o+1][bx[j]+1][k]>i.ans)
						qwq[o+1].emplace_back(bx[j]+1,k,
							ans[o+1][bx[j]+1][k]=i.ans);
				if(i.j<=uy[o][j])uy[o][j]=i.j-1;
			}
			i.ans+=a[i.i][i.j];
			if(ans[o][i.i+1][i.j]>i.ans)
				q.emplace(i.i+1,i.j,ans[o][i.i+1][i.j]=i.ans);
			if(ans[o][i.i][i.j+1]>i.ans)
				q.emplace(i.i,i.j+1,ans[o][i.i][i.j+1]=i.ans);
		}
	}
	printf("%lld",minn);
}