ZJOI2016 旅行者 题解
题目大意：
给定一个 \(n\times m\) 的网格图，相邻的四连通的点之间有给定边权的双向边，有 \(Q\) 个离线询问，问两个点之间的最短路。
\(n\times m\le 2\times 10^4,Q\le 10^5\)。
发现了吗？和上次省选组的三角剖分那道题很像，这种平面图上的最短路很有可能是分治。
考虑每次把矩形割成两半，分治处理询问。
如果询问在分割线两侧，那么路径一定跨过分割线，一定形如 \((x,s)+(s,y)\)，其中 \(s\) 为分割线上的点，于是枚举分割线上的点，对全图跑最短路。
如果询问在分割线同侧，对于路径不跨过的直接递归处理完了，但有可能路径仍跨过分割线，此时一定形如 \((x,s)+(s,y)\)，是同理的。
注意我们需要每次割边长较长的一边才能保证复杂度正确。
考虑计算时间复杂度，我们实际可以把矩形看做 \(n\times n\) 的正方形，每次分治两层可以得到 \(4\) 个 \((n/2)\times (n/2)\) 的正方形。
\[T(n)=4T(n/2)+O(n^3\log (n^2))+O(Qn) \]根据主定理 \(a=4,b=2,d>3\)，因此 \(\log _b a<d\)，所以时间复杂度为 \(O(n^3\log (n^2)+Qn)\)。
设 \(T=nm\le 2\times 10^4\)，那么复杂度为 \(O(T\sqrt T\log T+QT)\)。
AC 代码，使用动态数组实现：
const int maxq=1e5+5;
const int inf=0x3f3f3f3f;
int ans[maxq];
struct qry{
int x1,y1,x2,y2,num;
};
void solve(int n,int m,vector<vector<int>> &r,vector<vector<int>> &c,vector<qry> &q){
if(!q.size())return;
if(n<m){
for(auto &i:q)swap(i.x1,i.y1),swap(i.x2,i.y2);
vector<vector<int>> nr(m+1,vector<int>(n+1,0));
vector<vector<int>> nc(m+1,vector<int>(n+1,0));
fo(i,1,n)fo(j,1,m-1)nc[j][i]=r[i][j];
fo(i,1,n-1)fo(j,1,m)nr[j][i]=c[i][j];
r=nr,c=nc;
swap(n,m);
}
if(n==1){
for(auto i:q)ans[i.num]=0;
return;
}
vector<qry> q1,q2;
int mid=n/2;
for(auto i:q){
if(i.x1<=mid && i.x2<=mid) q1.push_back(i);
else if(i.x1>mid && i.x2>mid) q2.push_back({i.x1-mid,i.y1,i.x2-mid,i.y2,i.num});
}
vector<vector<int>> r1(mid+1,vector<int>(m+1,0));
vector<vector<int>> r2(n-mid+1,vector<int>(m+1,0));
vector<vector<int>> c1(mid+1,vector<int>(m+1,0));
vector<vector<int>> c2(n-mid+1,vector<int>(m+1,0));
fo(i,1,mid)fo(j,1,m-1)r1[i][j]=r[i][j];
fo(i,1,mid-1)fo(j,1,m)c1[i][j]=c[i][j];
fo(i,mid+1,n)fo(j,1,m-1)r2[i-mid][j]=r[i][j];
fo(i,mid+1,n-1)fo(j,1,m)c2[i-mid][j]=c[i][j];
solve(mid,m,r1,c1,q1),solve(n-mid,m,r2,c2,q2);
fo(i,1,m){
vector<vector<int>> dis(n+1,vector<int>(m+1,inf));
vector<vector<bool>> vis(n+1,vector<bool>(m+1,false));
dis[mid][i]=0;
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<>> p;
p.push({0,{mid,i}});
while(p.size()){
auto u=p.top().second; p.pop();
if(vis[u.first][u.second]) continue;
vis[u.first][u.second]=1;
auto update=[&](int x,int y,int d)->void{
if(dis[x][y]>d)dis[x][y]=d,p.push({d,{x,y}});
};
if(u.first>1)update(u.first-1,u.second,c[u.first-1][u.second]+dis[u.first][u.second]);
if(u.first<n)update(u.first+1,u.second,c[u.first][u.second]+dis[u.first][u.second]);
if(u.second>1)update(u.first,u.second-1,r[u.first][u.second-1]+dis[u.first][u.second]);
if(u.second<m)update(u.first,u.second+1,r[u.first][u.second]+dis[u.first][u.second]);
}
for(auto j:q){
ans[j.num]=min(ans[j.num],dis[j.x1][j.y1]+dis[j.x2][j.y2]);
}
}
}
signed main(){
int n,m,Q;
read(n,m);
vector<vector<int>> r(n+1,vector<int>(m+1,0));
vector<vector<int>> c(n+1,vector<int>(m+1,0));
fo(i,1,n)fo(j,1,m-1)read(r[i][j]);
fo(i,1,n-1)fo(j,1,m)read(c[i][j]);
read(Q);
vector<qry> q(Q);
fu(i,0,Q){
read(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
q[i].num=i+1;
ans[i+1]=inf;
}
solve(n,m,r,c,q);
fo(i,1,Q)write(ans[i],'\n');
return 0;
}