@description@
小 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) 最少需要花多少时间。
输入格式
第一行包含两个正整数 n,m，表示城市的大小。
接下来 n 行，每行包含 m-1 个整数，第 i 行第 j 个正整数表示从一个路口到另一个路口的时间 r(i,j)。
接下来 n-1 行，每行包含 m 个整数，第 i 行第 j 个正整数表示从一个路口到另一个路口的时间 c(i,j)。
接下来一行，包含一个正整数 q，表示小 Y 的询问个数。
接下来 q 行，每行包含四个正整数 x1,y1,x2,y2，表示两个路口的位置。
输出格式
输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
样例输入
2 2
2
3
6 4
2
1 1 2 2
1 2 2 1
样例输出
6
7
数据范围与提示
对于所有的测试数据，n*m <= 2*10^4，保证相邻路口之间的时间不超过 10^4，即 1<=r(i, j), c(i, j)<=10^4。
@solution@
显然不能每个点对都跑一遍最短路。
注意到在网格图中，对于两个点 (x1, y1), (x2, y2)，它们的最短路必然要跨越 x1 ~ x2 之间的行与 y1 ~ y2 之间的列。
然后我们考虑分治：
假如当前分治到的矩阵为 p*q，为了防止被卡，我们每次选取 max(p, q) 进行切割。
设切割的中线为 mid，枚举 mid 这条线上的所有点 k 求最短路。于是我们可以求得经过 mid 这条线中所有的路径中的最短路。
都在 mid 的同一边的，也需要统计经过 mid 的路径，不然会漏掉一些路径。
那么接下来就是不经过 mid 的那些路径，于是就以 mid 为界分为两部分，然后两部分分别递归下去。
如果某个询问跨越了 mid，就不把这个询问往下传了。否则就往它所在的那部分传。
复杂度？据说是 \(O(S\sqrt{S}\log S)\)（其中 S = n*m 为总点数）。
感知一下：当 \(n = m = \sqrt{S}\) 时取得最值。此时的复杂度就是如上的复杂度（log 是最短路的复杂度）。
@accepted code@
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 20000;
const int MAXQ = 100000;
const int INF = (1<<30);
struct edge{
int to, dis;
edge *nxt;
}edges[4*MAXN + 5], *adj[MAXN + 5], *ecnt = &edges[0];
void addedge(int u, int v, int w) {
edge *p = (++ecnt);
p->to = v, p->dis = w, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->dis = w, p->nxt = adj[v], adj[v] = p;
}
int n, m, q;
inline int id(int x, int y) {
return (x - 1)*m + y;
}
struct query{
int x1, y1, x2, y2, u, v, ind;
query(int _x1=0, int _y1=0, int _x2=0, int _y2=0, int _i=0) :
x1(_x1), y1(_y1), x2(_x2), y2(_y2), u(id(x1, y1)), v(id(x2, y2)), ind(_i) {}
}qry[MAXQ + 5];
bool tag[MAXN + 5];
int num[MAXN + 5], rev[MAXN + 5], tot;
int dis[MAXN + 5], hp[MAXN + 5], f[MAXN + 5];
void update(int x, int k) {
f[rev[x]] = k;
while( x ) {
hp[x] = rev[x];
if( (x<<1) <= tot && f[hp[x]] > f[hp[x<<1]] )
hp[x] = hp[x<<1];
if( (x<<1|1) <= tot && f[hp[x]] > f[hp[x<<1|1]] )
hp[x] = hp[x<<1|1];
x >>= 1;
}
}
void dijkstra(int s) {
update(num[s], dis[s] = 0);
while( f[hp[1]] != INF ) {
int x = hp[1];
// printf("! %d %d\n", dis[x], x);
update(num[x], INF);
for(edge *p=adj[x];p;p=p->nxt) {
if( !tag[p->to] ) continue;
if( dis[x] + p->dis < dis[p->to] )
update(num[p->to], dis[p->to] = dis[x] + p->dis);
}
}
}
int ans[MAXQ + 5];
void solve(int l, int r, int u, int d, int q) {
// printf("! %d %d %d %d : %d\n", l, r, u, d, q);
if( l > r || u > d || !q ) return ;
if( r - l > d - u ) {
int mid = (l + r) >> 1; tot = 0;
for(int i=l;i<=r;i++)
for(int j=u;j<=d;j++) {
tag[id(i, j)] = true;
num[id(i, j)] = (++tot), hp[tot] = id(i, j), rev[tot] = id(i, j);
}
for(int i=u;i<=d;i++) {
for(int x=l;x<=r;x++)
for(int y=u;y<=d;y++)
dis[id(x, y)] = INF;
dijkstra(id(mid, i));
for(int j=1;j<=q;j++)
ans[qry[j].ind] = min(ans[qry[j].ind], dis[qry[j].u] + dis[qry[j].v]);
}
for(int i=l;i<=r;i++)
for(int j=u;j<=d;j++)
tag[id(i, j)] = false;
int p = 0;
for(int i=1;i<=q;i++)
if( qry[i].x1 < mid && qry[i].x2 < mid )
swap(qry[++p], qry[i]);
solve(l, mid - 1, u, d, p);
int tmp = p + 1; p = 0;
for(int i=tmp;i<=q;i++)
if( qry[i].x1 > mid && qry[i].x2 > mid )
swap(qry[++p], qry[i]);
solve(mid + 1, r, u, d, p);
}
else {
int mid = (u + d) >> 1; tot = 0;
for(int i=l;i<=r;i++)
for(int j=u;j<=d;j++) {
tag[id(i, j)] = true;
num[id(i, j)] = (++tot), hp[tot] = id(i, j), rev[tot] = id(i, j);
}
for(int i=l;i<=r;i++) {
for(int x=l;x<=r;x++)
for(int y=u;y<=d;y++)
dis[id(x, y)] = INF;
dijkstra(id(i, mid));
for(int j=1;j<=q;j++)
ans[qry[j].ind] = min(ans[qry[j].ind], dis[qry[j].u] + dis[qry[j].v]);
}
for(int i=l;i<=r;i++)
for(int j=u;j<=d;j++)
tag[id(i, j)] = false;
int p = 0;
for(int i=1;i<=q;i++)
if( qry[i].y1 < mid && qry[i].y2 < mid )
swap(qry[++p], qry[i]);
solve(l, r, u, mid - 1, p);
int tmp = p + 1; p = 0;
for(int i=tmp;i<=q;i++)
if( qry[i].y1 > mid && qry[i].y2 > mid )
swap(qry[++p], qry[i]);
solve(l, r, mid + 1, d, p);
}
}
int main() {
scanf("%d%d", &n, &m);
int cnt = 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[id(i, j)] = INF;
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++) {
int x; scanf("%d", &x);
addedge(id(i, j), id(i, j + 1), x);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++) {
int x; scanf("%d", &x);
addedge(id(i, j), id(i + 1, j), x);
}
scanf("%d", &q);
for(int i=1;i<=q;i++) {
int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
qry[i] = query(x1, y1, x2, y2, i), ans[i] = INF;
}
solve(1, n, 1, m, q);
for(int i=1;i<=q;i++)
printf("%d\n", ans[i]);
}@details@
ZJOI 的题都是神仙题 * 1。
我也不知道为什么我常数这么大。。。