题目
题目链接：https://www.luogu.com.cn/problem/P3350
小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有 (n) 条从东到西的道路和 (m) 条从南到北的道路，这些道路两两相交形成 (n imes m) 个路口 ((i,j))， ((1leq ileq n,1leq jleq m))
她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口 ((i,j)) 到路口 ((i,j+1)) 需要时间 (r(i,j)) ，从路口 ((i,j)) 到路口 ((i+1,j)) 需要时间 (c(i,j)) 。注意这里的道路是双向的。小 Y 有 (q) 个询问，她想知道从路口 ((x1,y1)) 到路口 ((x2,y2)) 最少需要花多少时间。
(n imes mleq 2 imes 10^4)，(qleq 10^5)。
思路
网格图上分治的套路。
对于一个 (n imes m) 的矩形，假设 (ngeq m)。考虑第 (mid=frac{1+n}{2}) 行的贡献。
从这一行的 (m) 个点开始分别跑最短路，枚举所有属于该子矩形的询问更新答案。如果询问的两个点都在 ([1,mid-1]) 行就往上继续分治；如果都在 ([mid+1,n]) 行就往下分治，否则就不用继续分下去了。
复杂度不会证。看题解说是 (O(nmsqrt{nm}log (nm)))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010,Inf=1e9;
int n,m,Q,ans[N];
vector<int> r[N],c[N],dis[N],vis[N];
struct node
{
int x1,y1,x2,y2,id;
}a[N],b[N];
struct node1
{
int dis,x,y;
friend bool operator <(node1 x,node1 y)
{
return x.dis>y.dis;
}
};
void dij(int sx,int sy,int lx,int rx,int ly,int ry)
{
for (int i=lx;i<=rx;i++)
for (int j=ly;j<=ry;j++)
dis[i][j]=Inf,vis[i][j]=0;
priority_queue<node1> q;
q.push((node1){0,sx,sy}); dis[sx][sy]=0;
while (q.size())
{
int x=q.top().x,y=q.top().y; q.pop();
if (vis[x][y]) continue;
vis[x][y]=1;
if (x<rx && dis[x+1][y]>dis[x][y]+c[x][y])
dis[x+1][y]=dis[x][y]+c[x][y],q.push((node1){dis[x+1][y],x+1,y});
if (x>lx && dis[x-1][y]>dis[x][y]+c[x-1][y])
dis[x-1][y]=dis[x][y]+c[x-1][y],q.push((node1){dis[x-1][y],x-1,y});
if (y<ry && dis[x][y+1]>dis[x][y]+r[x][y])
dis[x][y+1]=dis[x][y]+r[x][y],q.push((node1){dis[x][y+1],x,y+1});
if (y>ly && dis[x][y-1]>dis[x][y]+r[x][y-1])
dis[x][y-1]=dis[x][y]+r[x][y-1],q.push((node1){dis[x][y-1],x,y-1});
}
}
void solve(int lx,int rx,int ly,int ry,int ql,int qr)
{
if (ql>qr || lx>rx || ly>ry || (lx==rx && ly==ry)) return;
if (rx-lx>=ry-ly)
{
int mid=(lx+rx)>>1,pl=ql-1,pr=qr+1;
for (int i=ly;i<=ry;i++)
{
dij(mid,i,lx,rx,ly,ry);
for (int j=ql;j<=qr;j++)
ans[a[j].id]=min(ans[a[j].id],dis[a[j].x1][a[j].y1]+dis[a[j].x2][a[j].y2]);
}
for (int i=ql;i<=qr;i++)
{
if (max(a[i].x1,a[i].x2)<mid) b[++pl]=a[i];
if (min(a[i].x1,a[i].x2)>mid) b[--pr]=a[i];
}
for (int i=ql;i<=qr;i++) a[i]=b[i];
solve(lx,mid-1,ly,ry,ql,pl);
solve(mid+1,rx,ly,ry,pr,qr);
}
else
{
int mid=(ly+ry)>>1,pl=ql-1,pr=qr+1;
for (int i=lx;i<=rx;i++)
{
dij(i,mid,lx,rx,ly,ry);
for (int j=ql;j<=qr;j++)
ans[a[j].id]=min(ans[a[j].id],dis[a[j].x1][a[j].y1]+dis[a[j].x2][a[j].y2]);
}
for (int i=ql;i<=qr;i++)
{
if (max(a[i].y1,a[i].y2)<mid) b[++pl]=a[i];
if (min(a[i].y1,a[i].y2)>mid) b[--pr]=a[i];
}
for (int i=ql;i<=qr;i++) a[i]=b[i];
solve(lx,rx,ly,mid-1,ql,pl);
solve(lx,rx,mid+1,ry,pr,qr);
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
r[i].push_back(0); c[i].push_back(0);
for (int j=0;j<=m;j++)
dis[i].push_back(0),vis[i].push_back(0);
}
for (int i=1;i<=n;i++)
for (int j=1,x;j<m;j++)
scanf("%d",&x),r[i].push_back(x);
for (int i=1;i<n;i++)
for (int j=1,x;j<=m;j++)
scanf("%d",&x),c[i].push_back(x);
scanf("%d",&Q);
for (int i=1;i<=Q;i++)
{
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
a[i].id=i; ans[i]=Inf;
if (a[i].x1==a[i].x2 && a[i].y1==a[i].y2) ans[i]=0;
}
solve(1,n,1,m,1,Q);
for (int i=1;i<=Q;i++)
cout<<ans[i]<<"
";
return 0;
}