自动搬运

查看原文

来自洛谷，原作者为

	zcysky 消え去る花かがやく息吹

搬运于2025-08-24 22:00:33，当前版本为作者最后更新于2018-10-26 21:03:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先最直接的做法是把所有可行的点直接连边，求一个最短路。

我们发现每一个点的连边是一段二维的区间，总共有 $O(n^2)$ 个点，所以总共会有 $O(n^4)$ 的边，不可接受。

我们考虑如何优化：

优化连边

首先最套路的办法，我们发现我们是一个点向一个区间连边。网络流的知识告诉我们，点向区间的连边可以使用线段树进行优化，于是这样就可以过了。 所以我们可以每一行建一个线段树，行内优化连边。

这样做的复杂度，点数是 $O(n^2)$ 的，边数原本是 $O(n^4)$ 的，使用线段树优化后降为$O(n^3logn)$ ,使用dijkstra算法求最短路，复杂度：

$O(n^3lognlog(n^3logn))$

用人话说，叫做 $O(能过)$

拆点

这个做法是目前网上最常见的做法。我们定义一个状态 $dp[i][j][k]$ 表示到达点 $(i,j)$ ，剩余的能量是 $k$ ，每走一格需要消耗1点能量，到达一个点相当于补充了 $a[i][j]$ 点能量。

所以一个点向外只有五种转移，分别是上下左右和不动。用这个东西跑最短路就可以了。

考虑到 $a[i][j]$ 还是很小的，所以这么做还是可以跑过去的。不过在bzoj上要跑25s左右。

并查集优化

这个做法是一个比较玄的科技，在此之前我还真的没有见过……

这也应该是本题目前的最优做法。

首先看一个弱化版的题：http://acm.hdu.edu.cn/showproblem.php?pid=5361

我们发现这个题是本题的一维情况，先来解决这个一维的问题。

考虑到一个点的连边是 $[L_i,R_i]$ 内的所有点。我们从一个端点开始跑最短路，那么如果一个点被二次进入（相当于“回头”），这个点必然不会被更新，因为相当于我们绕了几步又绕回来了，我们如果能想一个办法跳过这些点，就可以获得一个很优越的复杂度。

当年多校考场上很多选手是维护了一个set，以此判断当前点是否被更新。然而有一个更优美的做法是并查集：我们把已经更新的点放进一个集合内，根节点指向最右边节点的下一个点。这样当我们二次进入这个节点时，可以 $O(1)$ 地跳过当前所有节点。（因为第一次遍历完这个已更新集合的最后一个点时，这个并查集相当于进行了一次路径压缩，同时不会有新的节点加入，因此可以认为接下来的访问的复杂度都是 $O(1)$）

那么我们推广到这个题，沿用线段树的办法，我们把每一列建一个并查集，然后维护这一列哪些点已经被访问过。

然而如果直接加上并查集的话，我们忽略了一个重要条件：已经更新过的点不能被更新第二次，这是本算法正确的充要条件。

考虑我们从起点出发，找到一个点跳过去，这一个区域内的所有点都是等价的，因此会盲目的跳，这一个区域内的点（下面称作某一点的子节点）他们自己的子节点和这一区域内别的点的子节点是会相交的，这一片相交的区域，如果我们使用传统的最短路算法就会被多次更新，因为第一次进入这些点是没有决策的。

那么我们考虑更改边权，我们把跳到的点的 $a[i][j]$ 也算进边权，这样就是正确的了。

证明考虑数学归纳：

从起点出发，跳到一个 $a[i][j]$ 最小的点，到他的路径必然是最优的。

从该节点出发，跳到该节点的子节点也必然是最优的。

如果跳到了一个访问过的节点，那么当前的跳法必然是在之前最优选择完了之后的次优决策转移过来的，因此必然不会被更新。

所以这样做保证了更新过的点不会被更新第二次，就可以使用并查集优化了。

提供并查集优化的代码：

#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);}
template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);}
template<typename T> inline T sqr(T x){return x*x;}
template<typename T> inline void checkmax(T &x,T y){x=max(x,y);}
template<typename T> inline void checkmin(T &x,T y){x=min(x,y);}
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){
    A ans=1;
    for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
    return ans;
}
struct FastIO{
    static const int S=1310720;
    int wpos;char wbuf[S];
    FastIO():wpos(0) {}
    inline int xchar(){
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len)pos=0,len=fread(buf,1,S,stdin);
        if(pos==len)return -1;
        return buf[pos++];
    }
    inline int read(){
        int c=xchar(),x=0;
        while(c<=32&&~c)c=xchar();
        if(c==-1)return -1;
        for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
        return x;
    }
}io;
#define read io.read
const int N=160;
int dis[3][N][N],fa[N][N],a[N][N],b[N][N],vis[N][N],n,m;
inline int find(int *fa,int x){return fa[x]?fa[x]=find(fa,fa[x]):x;}
struct Node{
	int d,x,y;
};
inline bool operator <(Node a,Node b){return a.d>b.d;}
inline Node make_Node(int d,int x,int y){
	Node cur;cur.d=d;cur.x=x;cur.y=y;return cur;
}
priority_queue<Node> Q;
const int inf=1e9+7;
inline void dijkstra(int dis[N][N],Node s){
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=inf;
	dis[s.x][s.y]=0;
	memset(fa,0,sizeof(fa));memset(vis,0,sizeof(vis));
	while(!Q.empty())Q.pop();
	Q.push(make_Node(a[s.x][s.y],s.x,s.y));
	fa[s.x][s.y]=s.y+1;
	while(!Q.empty()){
		Node u=Q.top();Q.pop();
		int x=u.x,y=u.y;
		if(vis[x][y])continue;
		vis[x][y]=1;
		int lx=max(1,x-b[x][y]),rx=min(n,x+b[x][y]);
		for(int i=lx;i<=rx;i++){
			int len=b[x][y]-abs(i-x);
			int up=max(1,y-len),dw=min(m,y+len);
			for(int j=find(fa[i],up);j<=dw;j=find(fa[i],j)){
				if(dis[i][j]>dis[x][y]+a[x][y]){
					dis[i][j]=dis[x][y]+a[x][y];
					Q.push(make_Node(dis[i][j]+a[i][j],i,j));
				}
				fa[i][j]=j+1;
			}
		}
	}
	
}
Node st[10];
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
	for(int i=0;i<3;i++)st[i].x=read(),st[i].y=read();
	for(int i=0;i<3;i++)dijkstra(dis[i],st[i]);
	int mn=inf,mnpos=-1;
	for(int i=0;i<3;i++){
		int cur=0;
		for(int j=0;j<3;j++)cur+=dis[j][st[i].x][st[i].y];
		if(cur<mn)mn=cur,mnpos=i;
	}
	if(mnpos==-1)return puts("NO"),0;
	if(mnpos==0)puts("X");
	if(mnpos==1)puts("Y");
	if(mnpos==2)puts("Z");
	printf("%d\n",mn);
}