看了题解打的，但不知道为什么tle了附加点。

就是对于当前矩形，选择较短的中轴做最短路，之后处理一下询问，之后分治两边。

感觉跟2009wc最短路问题类似啊。

我的spfa应该没问题(还加了pairing_heap优化)

点(x,y)标号为(x-1)*m+y

#include<cstdio>

#define r_top 10000000
char ch[r_top],*now_r=ch;
void read(int &x)
{
    while (*now_r<'0') ++now_r;
    for (x=*now_r-'0';*++now_r>='0';)
     x=(x<<1)+(x<<3)+*now_r-'0';
}

#define chmin(x,y) if(x>y)x=y;
#define oo 1000000000
#define N 20100
#define Q 100100
#define add_e(x,y) l[++e]=(edge){y,t[x],len};t[x]=e;
#define add_(x,y) add_e(x,y) add_e(y,x)
int t[N];
struct edge
{
    int to,next,len;
}l[N<<2];int e;

int n,m,i,j,k,x,y,len;
struct Query
{ int x1,y1,x2,y2,id1,id2;
  bool r() 
  { read(x1);read(y1);read(x2);read(y2);
    id1=(x1-1)*m+y1;id2=(x2-1)*m+y2; //两个点的标号
    return id1!=id2;//如果一样就ans=0
  }
}query[Q];
int q[Q],ans[Q];
int g[N];//距离
bool in[N];//in=1表示在当前区间内

int head[N],next[N],*dy[N];
#define fu(x,y) {dy[y]=&x;x=y;}
#define _fu(x,y) {dy[y]=x;*x=y;}
void merge(int &x,int y)
{
    if (g[x]<g[y])
    {
        fu(next[y],head[x]);fu(head[x],y);
    }
    else
    {
        fu(next[x],head[y]);fu(head[y],x);
        x=y;
    }
}
void merges(int &x)
{
    int y=next[x],r;
    while (y)
    {
        r=next[y];
        merge(x,y);
        y=r;
    }
    next[x]=0;
}
void spfa(int x)
{
    int rt=x;g[x]=0;
    do
    {
        x=rt;merges(rt=head[rt]);
        head[x]=next[x]=0;dy[x]=0;
        for (int i=t[x],y;i;i=l[i].next)
        if (in[y=l[i].to]&&g[y]>g[x]+l[i].len)
        {
            g[y]=g[x]+l[i].len;
            if (y==rt) continue;
            if (!rt) {rt=y;continue;}
            if (dy[y]!=0) _fu(dy[y],next[y]);
            merge(rt,y);
        }
    }while (rt);
}

int o,q1[Q],q2[Q];
void solve(int lx,int rx,int ly,int ry,int l,int r)
{
    static int st[N],top;//当前区间内节点 
    if (l>r) return ;
    int numx=rx-lx+1,numy=ry-ly+1;
    x=(lx-1)*m+ly;
    for (i=1;i<=numx;++i,x+=m)
    for (j=0;j<numy;++j) 
     in[st[++top]=x+j]=1;
    if (numx<numy)
    {
        int mid=ly+ry>>1;
        x=(lx-1)*m+mid;//中轴最上面的坐标
        for (o=1;o<=numx;++o,x+=m)//每次往下移
        {
            for (i=1;i<=top;++i) g[st[i]]=oo;
            spfa(x);
           for (j=l;j<=r;++j)
           {
              y=q[j];
              chmin(ans[y],g[query[y].id1]+g[query[y].id2]);
           }
        }
        while (top) in[st[top--]]=0;
        int h1=0,h2=0;
        for (j=l;j<=r;++j) 
        {
            y=q[j];
            if (query[y].y1<mid)
            {
                if (query[y].y2<mid) q1[++h1]=y;
            }
            else
            if (query[y].y1>mid)
            if (query[y].y2>mid) q2[++h2]=y;
        }
        int h=l-1;
        for (i=1;i<=h1;++i) q[++h]=q1[i];
        for (i=1;i<=h2;++i) q[++h]=q2[i];
        solve(lx,rx,ly,mid-1,l,l+h1-1);
        solve(lx,rx,mid+1,ry,l+h1,h);
    }
    else
    {
        int mid=lx+rx>>1;

        x=(mid-1)*m+ly;//中轴最左边的坐标 
        for (o=1;o<=numy;++o,++x)
        {
            for (j=1;j<=top;++j) g[st[j]]=oo;
            spfa(x);
         for (j=l;j<=r;++j)
         {
             y=q[j];
             chmin(ans[y],g[query[y].id1]+g[query[y].id2]);
         }
        }
        while (top) in[st[top--]]=0;
        int h1=0,h2=0;
        for (j=l;j<=r;++j) 
        {
            y=q[j];
            if (query[y].x1<mid)
            {
                if (query[y].x2<mid) q1[++h1]=y;
            }
            else
            if (query[y].x1>mid)
            if (query[y].x2>mid) q2[++h2]=y;
        }
        int h=l-1;
        for (i=1;i<=h1;++i) q[++h]=q1[i];
        for (i=1;i<=h2;++i) q[++h]=q2[i];
        solve(lx,mid-1,ly,ry,l,l+h1-1);
        solve(mid+1,rx,ly,ry,l+h1,h);
    }
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    fread(ch,1,r_top,stdin);
    read(n);read(m);
    for (i=1;i<=n;++i,++x)
    for (j=1;j<m;++j)
    {
        read(len);
        ++x;
        add_(x,x+1) 
    }
    x=0;
    for (i=1;i<n;++i)
    for (j=1;j<=m;++j) 
    {
        read(len);
        ++x;
        add_(x,x+m) 
    }
    int qnum;
    read(qnum);
    int top=0;
    for (i=1;i<=qnum;++i) 
    if (query[i].r())
    {
      ++top;    
      ans[q[top]=i]=oo;
    }
    solve(1,n,1,m,1,top);
    for (i=1;i<=qnum;++i) printf("%d\n",ans[i]);
}