本题来自2025年北京冬令营B组。考场无人AC，但是有几名北师大实验的同学（不点名）利用《旅行者》代码成功骗得80分。由于官方题解过于抽象，写题解以补充。
简要题意
给定 $m\times n$ 网格图（其中 $m \le 10$），水平竖直方向有带权边。$q$ 次询问两点间最短路。不强制在线，但正解使用了在线方法。
暴力
对于每次询问跑单源最短路 Dijkstra 即可。复杂度为 $\Theta(qnm\log nm)$。期望得分 $20$。
图分治
根据浙江2016省选《旅行者》的方法，考虑把所有操作离线下来进行分治处理。
通过从中间切割较长一边把图分成两个部分，则对于跨过分界线的查询，最短路径一定经过了分界线上的点。对于没有跨过分界线的查询，最短路径不一定经过分界线上的点。
于是从分界线上的点（共有 $\min(n, m)$个，显然小于 $\sqrt{nm}$）开始对全图跑 Dijkstra，每次松弛（即利用 Bellman Ford 公式更新）一个询问。
此时跨过分界线的询问已经找到答案。对于没有跨过边界线的查询，则递归到图的两侧分治处理即可。
根据lqy的题解，此做法复杂度为 $\Theta(nm\sqrt{nm}\log nm + q\sqrt{nm})$。期望得分 $80$。
这个方法的复杂度依靠保证每次分界线上的点数不超过 $\sqrt n$，在平面图和广义串并联图中有许多应用。
这里给一个旅行者的std：看谁没有改数据范围就交上去然后只有40分
https://wck-oj.netlify.app/status/2cfe4c30eb0340f5915e6dd46c5cd07b
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
//#define showlog
//#define fileio
using namespace std;
const int N = 2e4+3, M = 1e5+3;
typedef pair<int, int> pii;
int d[N], ans[M];
vector<pii> linj[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;
struct Query
{
int x1, y1, x2, y2, id;
} q[M], tmp[M];
int n, m, Q;
int inline lget(int x, int y)
{
return (x-1) * m + y;
}
pii inline rget(int p)
{
if(p % m == 0) return mp(p / m, m);
return mp(p / m + 1, p % m);
}
void inline dijkstra(int s, int x1, int x2, int y1, int y2)
{
memset(d, 0x7f, sizeof(d));
d[s] = 0;
pq.push(mp(0, s));
while(!pq.empty())
{
auto now = pq.top();
pq.pop();
for(auto i : linj[now.second])
{
pii p = rget(i.first);
if(p.first < x1 || p.first > x2 || p.second < y1 || p.second > y2)
continue;
if(d[i.first] > d[now.second] + i.second)
{
d[i.first] = d[now.second] + i.second;
pq.push(mp(d[i.first], i.first));
}
}
}
}
void solve(int x1, int x2, int y1, int y2, int l, int r)
{
if(l > r || x1 > x2 || y1 > y2)
return;
int dx = x2 - x1, dy = y2 - y1;
if(dx > dy)
{
int mid = (x1 + x2)>>1;
for(int j = y1; j <= y2; j++)
{
dijkstra(lget(mid, j), x1, x2, y1, y2);
#ifdef showlog
cerr << "Starting with [" << mid << "," << j << "] to [" << x1 << "," << x2 << "," << y1 << "," << y2 << "]:" << endl;
for(int x = x1; x <= x2; x++)
{
for(int y = y1; y <= y2; y++)
{
cerr << d[lget(x, y)] << " ";
}
cerr << endl;
}
#endif
for(int k = l; k <= r; k++)
{
auto &cur = q[k];
ans[cur.id] = min(ans[cur.id], d[lget(cur.x1, cur.y1)] + d[lget(cur.x2, cur.y2)]);
}
}
int lf = l - 1, rf = r + 1;
for(int i = l; i <= r; i++)
{
auto &cur = q[i];
if(cur.x1 < mid && cur.x2 < mid)
tmp[++lf] = cur;
else if(cur.x1 > mid && cur.x2 > mid)
tmp[--rf] = cur;
}
for(int i = l; i <= lf; i++)
{
q[i] = tmp[i];
}
for(int i = rf; i <= r; i++)
{
q[i] = tmp[i];
}
solve(x1, mid-1, y1, y2, l, lf);
solve(mid+1, x2, y1, y2, rf, r);
}
else
{
int mid = (y1 + y2)>>1;
for(int i = x1; i <= x2; i++)
{
dijkstra(lget(i, mid), x1, x2, y1, y2);
#ifdef showlog
cerr << "Starting with [" << i << "," << mid << "] to [" << x1 << "," << x2 << "," << y1 << "," << y2 << "]:" << endl;
for(int x = x1; x <= x2; x++)
{
for(int y = y1; y <= y2; y++)
{
cerr << d[lget(x, y)] << " ";
}
cerr << endl;
}
#endif
for(int k = l; k <= r; k++)
{
auto &cur = q[k];
ans[cur.id] = min(ans[cur.id], d[lget(cur.x1, cur.y1)] + d[lget(cur.x2, cur.y2)]);
}
}
int lf = l - 1, rf = r + 1;
for(int i = l; i <= r; i++)
{
auto &cur = q[i];
if(cur.y1 < mid && cur.y2 < mid)
tmp[++lf] = cur;
else if(cur.y1 > mid && cur.y2 > mid)
tmp[--rf] = cur;
}
for(int i = l; i <= lf; i++)
{
q[i] = tmp[i];
}
for(int i = rf; i <= r; i++)
{
q[i] = tmp[i];
}
solve(x1, x2, y1, mid-1, l, lf);
solve(x1, x2, mid+1, y2, rf, r);
}
}
int main()
{
ios::sync_with_stdio(false);
#ifdef fileio
freopen("tourist.in", "r", stdin);
freopen("tourist.out", "w", stdout);
#endif
#ifdef showlog
freopen("tourist.log", "w", stderr);
#endif
cin >> n >> m;
int w;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < m; j++)
{
cin >> w;
linj[lget(i, j)].pb(mp(lget(i, j+1), w));
linj[lget(i, j+1)].pb(mp(lget(i, j), w));
}
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> w;
linj[lget(i, j)].pb(mp(lget(i+1, j), w));
linj[lget(i+1, j)].pb(mp(lget(i, j), w));
}
}
cin >> Q;
for(int i = 1; i <= Q; i++)
{
cin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2;
q[i].id = i;
}
memset(ans, 0x7f, sizeof(ans));
solve(1, n, 1, m, 1, Q);
for(int i = 1; i <= Q; i++)
{
cout << ans[i] << endl;
}
return 0;
}根据ljc的题解，这代码改个假的 Dijkstra 就能在清橙上通过了……但如果想在其他OJ（如WCK OJ/Deeplearning OJ）上通过，我们还是得看正解啊。
线段树启动
旅行者的分治思路启示我们在 $m$ 较小时可以考虑只对 $n$ 进行分治。
于是，结合对线段树与分治关系的理解，我们可以考虑对 $n$ 一维开一棵线段树。
具体地，我们可以设 $F(l, r, x, y)$ 表示——从 $(l, x)$ 到 $(r, y)$ 的最短路径。我们可以在线段树上每个点开一个二维数组 $dp_{x,y}$，表示当前节点维护区间 $[l, r]$ 的 $F(l,r,x,y)$。
通过从中间切割较长一边把图分成两个部分，则对于跨过分界线的查询，最短路径一定经过了分界线上的点。
则根据图分治的原理，如果我们知道了左右两个儿子的维护区间信息 $[l, mid]$，$[mid+1,r]$（答案合并时同理），则可以通过枚举中间通过了哪一条横向边来更新出 $[l,r]$ 的区间信息，即采用如下公式：
$$
F(l,r,x,y) = \min_{a=1}^m F(l,mid,x,a) + A_{a,mid} + F(mid+1,r,a,y)
$$
其中 $A_{a,mid}$ 是题目中给定的横向边权值。
于是，问题只剩一个——怎样求出叶子节点的维护信息，即 $F(i,i,x,y)$。
反复横跳
通过画图，我们可以观察到对于从 $(i,x)$ 到 $(i, y)$ 的任意一条路径，可以利用其横穿过这两点确定的竖直直线的位置，划分成若干个全部位于这一直线左侧或右侧的路线段。
即这一条最短路径是由若干个不横穿过该直线的最短路径所拼接而成的。
还有一个小问题，如何将这些路径拼接起来呢？
我们考虑先从 $(i,x)$ 沿着简单路径走到 $(i,k)$ 等点位最后再走到 $(i,y)$ 的过程——这不就相当于在一个图上不断进行松弛操作寻找最短路吗？专业一点讲，这就是在求原先路径的传递闭包。直接对原来的路径邻接矩阵来一发 Floyd 即可轻松搞定。
于是，我们可以再次简化问题——只需要求出如何从 $(i,x)$ 只沿其所在竖线左侧（或右侧）到达 $(i,y)$ 的最短路径即可。
再次反复横跳
我们把左右两侧分开讨论：（最终路径即为两边取 $\min$）
- 设 $L(i,x,y)$ 表示从 $(i,x)$ 出发，中间经过的点横坐标均 $<i$，最终到达 $(i,y)$ 的最短路径。
- 设 $R(i,x,y)$ 表示从 $(i,x)$ 出发，中间经过的点横坐标均 $>i$，最终到达 $(i,y)$ 的最短路径。
先考虑左侧怎么求。
把定义进行转化，所求即为从 $(i,x)$ 出发，中间经过的点横坐标均 $\le i-1$，最终到达 $(i,y)$ 的最短路径。
注意到开始和结尾两条边一定是横向边，边权为定值，直接加入答案即可。
于是继续转化所求：从 $(i-1,x)$ 出发，中间经过的点横坐标均 $\le i-1$，最终到达 $(i-1,y)$ 的最短路径。
再次画图感受一下，同前文所述，这一条路径可以被分为若干个位于 $i-1$ 竖线左侧的最短路径。同理一发 Floyd 就可以求出传递闭包。
用公式形式化表述：
$$
L(i,x,y) = L'(i-1,x,y) + A_{x,i-1} + A_{y,i-1}
$$
注意这里需要判断一下沿着竖向边走的情况，在跑 Floyd 求传递闭包前对于相邻的节点直接加入贡献即可。
于是，我们可以成功地从左向右初始化出 $L(i,x,y)$，从右向左初始化出 $R(i,x,y)$，进而初始化出 $F(i,i,x,y)$。利用这个信息，我们可以成功建出线段树，然后区间合并就可以查到任意两个点之间的最短路径了。
进行复杂度分析，由于使用了 Floyd，同时区间合并需要枚举 $x,y,a$，时间复杂度为 $3$ 次方级别，即 $\Theta(nm^3+qm^3\log n)$。根据官方数据强度，期望得分 $95 \sim 100$。复杂度有待进一步优化。
向量乘矩阵优化
如果你写刚才的做法被卡常了（这种现象十分普遍），我们接着来看怎么进一步优化。
注意到复杂度瓶颈位于查询，我们考虑把查询离线？不用这么麻烦，反正都有线段树了。
对于每次查询，我们只需要知道从 $(l,x)$ 到 $(r,y)$ 的最短路，不需要知道从 $l$ 到 $r$ 的所有最短路。我们考虑只维护从 $(l,x)$ 出发的单源最短路。
设一个一维的向量，类似线段树二分的思路从左往右扫描线段树，每一次遇到合法区间就加入当前矩阵的贡献，此时每次加入只需要枚举 $y,a$ 就可以了。注意要特判第一次加入的区间，利用其贡献初始化出到达当前矩阵最右侧的最短路。
最终复杂度为 $\Theta(nm^3+qm^2\log n)$。代码很好写，可以顺利通过本题，数据点 $20$ 在评测机空闲情况下甚至可以跑到 $800\text{ms}$ 以内。
这题给我们的启发
首先，图上也是能分治的。
其次，图分治也是能套线段树的。
再其次，传递闭包这个概念也是学到了的。
相信经过这道题的洗礼，大家一定对最短路算法有了更加深刻全面的理解。
最后我们来发std。
std
https://wck-oj.netlify.app/status/174eebc8fda80c1438ffbd865a78979e
#include<bits/stdc++.h>
#define fileio
using namespace std;
const int M = 13, N = 1e5+3;
typedef unsigned long long ll;
const ll INF = 1e15;
ll a[M][N], b[M][N], le[N][M][M], ri[N][M][M], tr[N<<2][M][M], ans[M], tans[M];
int m, n, q;
bool flag = true;
void inline floyd(ll a[M][M])
{
for(int k = 1; k <= m; k++)
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
void inline cp(ll a[M][M], ll b[M][M])
{
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
b[i][j] = a[i][j];
}
void inline clr(ll a[M][M])
{
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
a[i][j] = i == j ? 0 : INF;
}
void inline Merge(int p, int mid)
{
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
tr[p][i][j] = INF;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
for(int k = 1; k <= m; k++)
tr[p][i][j] = min(tr[p][i][j], tr[p<<1][i][k] + a[k][mid] + tr[p<<1|1][k][j]);
}
void inline Updans(int p, int l, int r)//向量乘 优化（开头不必转移）
{
for(int i = 1; i <= m; i++)
tans[i] = INF;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
tans[i] = min(tans[i], ans[j] + (flag ? 0 : a[j][l-1]) + tr[p][j][i]);
for(int i = 1; i <= m; i++)
ans[i] = tans[i];
}
void Build(int p, int bl, int br)
{
if(bl == br)
{
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
tr[p][i][j] = min(le[bl][i][j], ri[bl][i][j]);
floyd(tr[p]);
return;
}
int m = (bl+br)>>1;
Build(p<<1, bl, m);
Build(p<<1|1, m+1, br);
Merge(p, m);
}
void Query(int p, int ql, int qr, int l, int r)
{
if(l > qr || r < ql)
return;
if(ql <= l && r <= qr)
{
Updans(p, l, r);
if(flag)
flag = false;
return;
}
int m = (l+r)>>1;
Query(p<<1, ql, qr, l, m);
Query(p<<1|1, ql, qr, m+1, r);
}
int main()
{
ios::sync_with_stdio(false);
#ifdef fileio
freopen("optimization.in", "r", stdin);
freopen("optimization.out", "w", stdout);
//freopen("optimization.log", "w", stderr);
#endif
cin >> m >> n >> q;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j < n; j++)
{
cin >> a[i][j];
}
}
for(int i = 1; i < m; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> b[i][j];
}
}
clr(le[0]);
for(int k = 1; k <= n; k++)
{
cp(le[k-1], le[k]);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
if(i != j)
le[k][i][j] += a[i][k-1] + a[j][k-1];
for(int i = 1; i < m; i++)
{
le[k][i][i+1] = min(le[k][i][i+1], b[i][k]);
le[k][i+1][i] = min(le[k][i+1][i], b[i][k]);
}
floyd(le[k]);
}
clr(ri[n+1]);
for(int k = n; k > 0; k--)
{
cp(ri[k+1], ri[k]);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++)
if(i != j)
ri[k][i][j] += a[i][k] + a[j][k];
for(int i = 1; i < m; i++)
{
ri[k][i][i+1] = min(ri[k][i][i+1], b[i][k]);
ri[k][i+1][i] = min(ri[k][i+1][i], b[i][k]);
}
floyd(ri[k]);
}
Build(1, 1, n);
for(int i = 1; i <= q; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if(y1 > y2)
{
swap(x1, x2);
swap(y1, y2);
}
for(int i = 1; i <= m; i++)
ans[i] = INF;
ans[x1] = 0;
flag = true;
Query(1, y1, y2, 1, n);
cout << ans[x2] << endl;
}
return 0;
}