![P3350 [ZJOI2016]旅行者](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "P3350 [ZJOI2016]旅行者")
题目描述
小Y来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有n条从东到西的道路和m条从南到北的道路，这些道路两两相交形成n*m个路口 (i,j)(1<=i<=n,1<=j<=m)。
她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口(i,j)到路口(i,j+1)需要时间 r(i,j)，从路口(i,j)到路口(i+1,j)需要时间c(i,j)。注意这里的道路是双向的。小Y有q个询问，她想知道从路口(x1,y1)到路口(x2,y2)最少需要花多少时间。
输入输出格式
输入格式：
第一行包含 2 个正整数n,m，表示城市的大小。接下来n行，每行包含m?1个整数，第i行第j个正整数表示从一个路口到另一个路口的时间r(i,j)。接下来n?1行，每行包含m个整数，第i行第j个正整数表示从一个路口到另一个路口的时间c(i,j)。接下来一行，包含1个正整数q，表示小Y的询问个数。接下来q行，每行包含4个正整数 x1,y1,x2,y2，表示两个路口的位置。
输出格式：
输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
输入输出样例
说明
题解:JudgeOnline/upload/201603/4456 sol.txt
// luogu-judger-enable-o2
//Pro:4456: [Zjoi2016]旅行者 //luogu开O2才能跑过..... //将询问离线
//对于rx-lx>ry-ly的矩形，我们对x分治，否则对y分治
//我们取矩形的中间线将矩形分成两部分，那么一个询问的两个点有可能分别在线的两侧，也可能在线的同侧
//如果在线的两侧，那么它们之间的路径肯定会经过线上的一个点
//所以我们对线上的每一个点跑最短路，更新当前矩形内所有询问的ans，这样两点在线的两侧的询问就处理完了
//对于两点在线的同侧的询问，它们的最短路可能过线，也可能不过线
//过线的情况在处理两点在线的两侧的时候已经更新过了，不过线的情况继续分治下去就可以了 //这样做的原因是一个询问的两个点一定会在某条线的两侧 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; inline int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} const int N=2e4+;
const int M=1e5+;
const int INF=0x3fffffff; #define poi(x,y) (x-1)*m+y int n,m,Q;
int dis[N],dist[N][],ans[M]; struct Query
{
int x,y,xx,yy,id;
}q[M],q1[M],q2[M]; struct Node
{
int dis,x,y;
Node(int a,int b,int c)
{
x=a,y=b,dis=c;
}
bool operator < (const Node &a) const
{
return dis>a.dis;
}
}; int cx[]={-,,,},cy[]={,,,-};
priority_queue<Node> que; bool vis[N];
void dijkstra(int sx,int sy,int lx,int rx,int ly,int ry)
{
int x,y,xx,yy;
for(int i=lx;i<=rx;++i)
for(int j=ly;j<=ry;++j)
dis[poi(i,j)]=INF,vis[poi(i,j)]=;
dis[poi(sx,sy)]=;
que.push(Node(sx,sy,));
while(!que.empty())
{
x=que.top().x,y=que.top().y;
que.pop();
if(vis[poi(x,y)])
continue;
vis[poi(x,y)]=;
for(int i=;i<;++i)
{
xx=x+cx[i],yy=y+cy[i];
if(xx>=lx&&xx<=rx&&yy>=ly&&yy<=ry&&dis[poi(xx,yy)]>dis[poi(x,y)]+dist[poi(x,y)][i])
{
dis[poi(xx,yy)]=dis[poi(x,y)]+dist[poi(x,y)][i];
que.push(Node(xx,yy,dis[poi(xx,yy)]));
}
}
}
} void solve(int lx,int rx,int ly,int ry,int lq,int rq)
{
if(lq>rq)
return;
if(lx==rx&&ly==ry)
{
for(int i=lq;i<=rq;++i)
ans[q[i].id]=;
return;
}
if(rx-lx>ry-ly)
{
int mid=(lx+rx)>>,h1=,h2=;
for(int i=ly;i<=ry;++i)
{
dijkstra(mid,i,lx,rx,ly,ry);
for(int j=lq;j<=rq;++j)
ans[q[j].id]=min(ans[q[j].id],dis[poi(q[j].x,q[j].y)]+dis[poi(q[j].xx,q[j].yy)]);
}
for(int i=lq;i<=rq;++i)
{
if(q[i].x<=mid&&q[i].xx<=mid)
q1[++h1]=q[i];
else if(q[i].x>mid&&q[i].xx>mid)
q2[++h2]=q[i];
}
for(int i=;i<=h1;++i)
q[lq+i-]=q1[i];
for(int i=;i<=h2;++i)
q[lq+h1-+i]=q2[i];
solve(lx,mid,ly,ry,lq,lq+h1-),solve(mid+,rx,ly,ry,lq+h1,lq+h1+h2-);
}
else
{
int mid=(ly+ry)>>,h1=,h2=;
for(int i=lx;i<=rx;++i)
{
dijkstra(i,mid,lx,rx,ly,ry);
for(int j=lq;j<=rq;++j)
ans[q[j].id]=min(ans[q[j].id],dis[poi(q[j].x,q[j].y)]+dis[poi(q[j].xx,q[j].yy)]);
}
for(int i=lq;i<=rq;++i)
{
if(q[i].y<=mid&&q[i].yy<=mid)
q1[++h1]=q[i];
else if(q[i].y>mid&&q[i].yy>mid)
q2[++h2]=q[i];
}
for(int i=;i<=h1;++i)
q[lq+i-]=q1[i];
for(int i=;i<=h2;++i)
q[lq+h1-+i]=q2[i];
solve(lx,rx,ly,mid,lq,lq+h1-),solve(lx,rx,mid+,ry,lq+h1,lq+h1+h2-);
}
} int main()
{
n=read(),m=read();
for(int i=;i<=n;++i)
for(int j=;j<m;++j)
dist[poi(i,j)][]=dist[poi(i,j+)][]=read();
for(int i=;i<n;++i)
for(int j=;j<=m;++j)
dist[poi(i,j)][]=dist[poi(i+,j)][]=read();
Q=read();
for(int i=;i<=Q;++i)
q[i].x=read(),q[i].y=read(),q[i].xx=read(),q[i].yy=read(),q[i].id=i;
memset(ans,0x3f,sizeof(ans));
solve(,n,,m,,Q);
for(int i=;i<=Q;++i)
printf("%d\n",ans[i]);
return ;
}