看了题解打的,但不知道为什么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]);
}