题解 P4473 【[国家集训队]飞飞侠】
首先最直接的做法是把所有可行的点直接连边，求一个最短路。
我们发现每一个点的连边是一段二维的区间，总共有
我们考虑如何优化：
优化连边
首先最套路的办法，我们发现我们是一个点向一个区间连边。网络流的知识告诉我们，点向区间的连边可以使用线段树进行优化，于是这样就可以过了。 所以我们可以每一行建一个线段树，行内优化连边。
这样做的复杂度，点数是
用人话说，叫做
拆点
这个做法是目前网上最常见的做法。我们定义一个状态
所以一个点向外只有五种转移，分别是上下左右和不动。用这个东西跑最短路就可以了。
考虑到
并查集优化
这个做法是一个比较玄的科技，在此之前我还真的没有见过……
这也应该是本题目前的最优做法。
首先看一个弱化版的题：http://acm.hdu.edu.cn/showproblem.php?pid=5361
我们发现这个题是本题的一维情况，先来解决这个一维的问题。
考虑到一个点的连边是
当年多校考场上很多选手是维护了一个set，以此判断当前点是否被更新。然而有一个更优美的做法是并查集：我们把已经更新的点放进一个集合内，根节点指向最右边节点的下一个点。这样当我们二次进入这个节点时，可以
那么我们推广到这个题，沿用线段树的办法，我们把每一列建一个并查集，然后维护这一列哪些点已经被访问过。
然而如果直接加上并查集的话，我们忽略了一个重要条件：已经更新过的点不能被更新第二次，这是本算法正确的充要条件。
考虑我们从起点出发，找到一个点跳过去，这一个区域内的所有点都是等价的，因此会盲目的跳，这一个区域内的点（下面称作某一点的子节点）他们自己的子节点和这一区域内别的点的子节点是会相交的，这一片相交的区域，如果我们使用传统的最短路算法就会被多次更新，因为第一次进入这些点是没有决策的。
那么我们考虑更改边权，我们把跳到的点的
证明考虑数学归纳：
从起点出发，跳到一个
从该节点出发，跳到该节点的子节点也必然是最优的。
如果跳到了一个访问过的节点，那么当前的跳法必然是在之前最优选择完了之后的次优决策转移过来的，因此必然不会被更新。
所以这样做保证了更新过的点不会被更新第二次，就可以使用并查集优化了。
提供并查集优化的代码：
#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);
}