WZK旅游题精讲：BFS无权图最短路、状态定义与队列去重

题库里编号 1996、标签写着 bfs、题面里一个代号 WZK 的旅行者要在一张图或一张地图上跑出最省事的那条路线——这类题我从入门一路写到带新人见得太多了。它的外壳是旅游内核是广度优先搜索BFS求无权图最短路考的不是你能不能背出模板而是你能不能把旅游这个生活化描述准确翻译成一张状态图再用最省的方法在图上按层推进。很多人三分钟敲完模板然后在一个vis标记的位置上卡掉两个小时最后发现逻辑没错、错在顺序。这篇东西想解决的就是这类问题拿到一个某人要去某个地方、问最少多少步/最少多少花费的题目怎么判断该不该用 bfs状态该怎么定义队列和去重怎么写才不炸内存不超时以及提交之后从 WA 到 AC 的那条排查链路该怎么走。适合刚学完 BFS 模板、能默写但一到变形题就发懵的同学也适合已经能写但对性能细节模棱两可的人。下面所有代码都是 C可以直接拿去改。1. WZK旅游这四个字里藏着的信息量1.1 为什么旅游类题目八成落在最短路模型上题目管这个叫旅游本质是在问从 A 到 B 最少付出多少。只要题目里出现最少最短最快至少几次这类字眼并且每一次行动的代价是一样的——走一格算一步、坐一趟车算一次、过一个城市算一天——那它就是一个边权全为 1 的图上的最短路问题标准解法就是广度优先搜索。这个判断很关键因为它直接决定了你该不该往 Dijkstra、SPFA、甚至 DP 的方向想。我见过不少人一看到最短路三个字就条件反射地写优先队列代码又长常数又大其实题目里每条边代价都是 1用优先队列属于纯纯的自我折磨。BFS 在边权相同的图上能保证第一次到达某点时的步数就是最小步数因为它是一层一层往外扩的先扩到的一定是层数浅的。生活化一点说往平静的水面丢一颗石子波纹一圈一圈往外推。第一圈到达的地方一定比第二圈到达的地方近。BFS 就是模拟这个波纹扩散过程队列就是这一圈还没处理完的点。你只要保证波纹不会重复扫同一片水面整个推进过程就是 O(VE) 的。1.2 BFS 能用的三个硬前提缺一个就白写我把这三个前提单独拎出来讲因为它们是你判断这题能不能用 BFS的唯一依据比背模板重要得多。第一所有边的代价必须相同通常是 1。如果题目里出现走平地花 1 天、爬山花 3 天这种差异化代价普通 BFS 立刻失效因为你没法保证先出队的节点代价更小。这时候要么把代价拆成多个虚拟节点要么直接换 0-1 BFS 或 Dijkstra。旅游题特别喜欢加这种设定读到某些路需要额外花费就要立刻警觉。第二必须有明确的、可枚举的状态。状态就是你当前所处的情况要能用有限个变量完整描述。网格题里是坐标(x, y)图论题里是节点编号u如果题目还有已经用了几次免费机会还剩多少油这类限制就要把这一维加进状态里。状态定义不全是 BFS 最隐蔽的错误来源——你的程序会跑得飞快答案就是不对。第三必须能判断这个状态我来过没有。重复访问同一个状态轻则答案变慢重则死循环。所以一定要有一个vis或者dist数组来记账。很多新手栽在忘记标记起点或者标记写在错误的位置后面第 3 节我会专门拆这个坑。这三条同时满足BFS 才是安全的。缺任何一条你写出来的东西可能在小样例上碰巧对一交大样例就原形毕露。2. 把题面翻译成状态图四个必须钉死的要素2.1 状态到底该存什么拿到题第一步不是敲代码是在纸上写清楚四件事状态是什么、起点是谁、终点是谁、一步能怎么走。这四件事写不明白代码写得再漂亮都是碰运气。先说状态。WZK 在某座城市和WZK 在某张地图的某个格子看起来是一回事落到代码上差别很大。前者状态就是一个整数u用邻接表存边后者状态是(x, y)二元组用方向数组在网格上挪动。这两套写法我下面各给一份模板别混着用。再说那些容易被漏掉的附加维度。题目里如果出现下面这些描述状态就要加一维题面描述状态需要多加的一维状态总数估算可以使用 k 次免费通行已用次数c取值 0..kV × (k1)体力/油量上限为 P剩余量r取值 0..PV × (P1)必须收集齐若干物品已收集集合的二进制掩码V × 2^m需要按顺序经过几个必经点已完成阶段编号V × 阶段数这个表看着简单但它决定了你的数组开多大、复杂度多少。我见过一道题加了一维已用免费次数之后状态数从 10^5 变成 10^6数组开小了直接 RE开大了 MLE卡在中间的滋味很难受。所以动手之前先算状态总数这是习惯问题。2.2 边的权值决定了你用哪种队列状态和转移定好之后看每条边的代价。这一步是个分叉口走错方向后面全错。代价全是 1用普通队列queue或者数组模拟队列最标准的 BFS。 代价只有 0 和 1 两种用双端队列deque这就是 0-1 BFS0 代价的走法塞队首1 代价的塞队尾保证队列近似单调。 代价是任意非负整数老老实实上 DijkstraBFS 帮不了你。旅游题最常出现的变形是第二种某段路不花钱瞬移免费换乘这就是 0 代价边。这时候如果你还用普通队列程序不会报错答案会偏大而且只在大数据上偏调起来非常恶心。看到免费不需花费直接到达这类字眼脑子里就该亮灯。至于路径连通性怎么表示网格题用方向数组图论题用邻接表或前向星。我给的建议是点数不超过 10^3 用邻接矩阵无所谓超过就用邻接表因为邻接矩阵在稠密图上省事但点数一大就爆内存。旅游类题目的地图经常是 n×m 网格n,m 上千此时节点数上百万千万别用二维矩阵建图。3. 手写队列与去重BFS 的性能全在这两个地方3.1 数组模拟队列的写法与容量估算先给结论竞赛里写 BFS我基本不用std::queue一律数组模拟。原因很实在——std::queue每次push/pop都有函数调用和内存分配的开销元素多的时候常数能差出两到三倍。而数组模拟队列就是两个下标head、tail在一个静态数组上滑动读写都在连续内存里对缓存极其友好。const int MAXS 1000005; // 状态总数的上限 int qx[MAXS], qy[MAXS]; // 分别存横纵坐标 int head 0, tail 0; qx[tail] sx; qy[tail] sy; tail; // 起点入队 while (head tail) { int x qx[head], y qy[head]; head; // 出队 // ... 扩展后继状态然后 qx[tail] nx; qy[tail] ny; tail; }队列容量怎么估原则只有一条队列里最多同时存在状态总数这么多个元素因为每个状态最多入队一次前提是你正确去重了。所以MAXS直接开到状态总数就行别抠抠搜搜开一半。网格题状态总数是n*m如果地图是 1000×1000那MAXS就是一千万两个 int 数组各 40MB加起来 80MB已经有点悬了。这时候有个很实用的技巧把二元状态压成一个整数。id x * m y队列只存int一个数组出队时再解回来x id / m, y id % m。存储直接减半而且取模除法的开销远比你想的小。再极端一点如果n*m不超过 2^31压成一个 int 完全没问题我甚至见过有人用位运算(x 11) | y来压缩前提是 m 不超过 2048。3.2 入队标记还是出队标记这是个送命题这一小节是我最想强调的地方因为我见过的 BFS 错误里一半以上出在这里。正确的做法是在节点入队的那一刻就标记它已访问而不是等它出队再标记。// 正确写法 while (head tail) { int u q[head]; for (每个后继 v) { if (vis[v]) continue; vis[v] true; // 入队前就标记 dist[v] dist[u] 1; q[tail] v; } }// 错误写法出队时才标记 while (head tail) { int u q[head]; if (vis[u]) continue; vis[u] true; // 太晚了 for (每个后继 v) { if (vis[v]) continue; q[tail] v; } }差别在哪在错误写法里同一个节点可能被多个不同的前驱重复塞进队列。假设一个格子有四个邻居都能到达它那它就会被 push 四次队列规模直接膨胀极端情况下比如稠密图能膨胀到边数级别复杂度从 O(VE) 劣化内存也跟着炸。更麻烦的是这道题如果是多组测试数据队列数组开得刚刚好一个膨胀就直接越界 RE。判断标准很简单只要你的算法是层序推进、第一次到达即最优标记就必须放在入队处。0-1 BFS 是个例外它靠dist松弛而不是靠vis同一个点确实可能多次入队那是另一套逻辑别混。3.3 多组数据下的时间戳去重旅游类题目很喜欢一个输入里塞多组地图问你每组的最小步数。这时候每次memset(vis, 0, sizeof(vis))看着没问题实际上如果vis开了一千万而每组地图只有 10×10那你十有八九的时间都花在清空一个根本没用到的巨大数组上。TLE 报出来的时候你会以为是 BFS 写得慢其实是 memset 拖的。解决办法是时间戳标记法vis数组存整型不再存 0/1而是存这是第几组数据访问的。int vis[MAXN][MAXN]; // 全局变量默认全 0 int stamp 0; for (int tc 1; tc T; tc) { stamp; // 每组数据用一个新时间戳 // 访问判断从 if (vis[nx][ny]) 变成 if (vis[nx][ny] stamp) // 标记从 vis[nx][ny] 1 变成 vis[nx][ny] stamp }这样就不需要任何清空操作一组数据一秒钟搞定。距离数组同理如果题目要输出步数可以另开一个dist数组并且用同样的时间戳技巧或者干脆把dist也编码进vis里用一个足够大的基数比如vis[id] stamp * BASE step读的时候取模——不过这种做法可读性差我不太推荐除非你被卡得很惨。注意时间戳法要求stamp单调递增且不溢出。int上限二十一亿一般测试组数远达不到但如果是交互式或者极端的多组比如十万组就用long long或者定期重置。4. 一份可以直接抄的 BFS 骨架含网格与邻接表两版4.1 网格版旅游地图的标准解法这是最贴合旅游意象的一版。地图上有可走格子和障碍问从起点到终点最少几步。#include bits/stdc.h using namespace std; const int MAXN 1005; int n, m, sx, sy, tx, ty; char g[MAXN][MAXN]; int dist[MAXN][MAXN]; int qid[MAXN * MAXN]; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int bfs() { if (sx tx sy ty) return 0; // 起点即终点别漏 int head 0, tail 0; int sid sx * m sy; qid[tail] sid; dist[sx][sy] 0; while (head tail) { int id qid[head]; int x id / m, y id % m; for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; if (nx tx ny ty) return dist[nx][ny]; qid[tail] nx * m ny; } } return -1; // 不可达 }几个细节值得单独说。dist初始化为 -1 有两个作用一是表示没访问过二是让不可达的格子自然区分于步数为 0 的起点。用 0 初始化就会踩到起点步数也是 0怎么判断它访问过没有的坑。起点单独先判一次相等是因为如果起点等于终点循环里永远碰不到终点判断因为起点已经处理完了会返回 -1。4.2 邻接表版城市之间往返的情形如果题目给的是城市之间的通路用前向星建图更合适。const int MAXN 100005, MAXM 400005; int head[MAXN], nxt[MAXM], to[MAXM], ecnt 0; int dist[MAXN], q[MAXN]; void addEdge(int u, int v) { to[ecnt] v; nxt[ecnt] head[u]; head[u] ecnt; } int bfs(int s, int t) { fill(dist, dist MAXN, -1); int h 0, tl 0; q[tl] s; dist[s] 0; while (h tl) { int u q[h]; if (u t) return dist[u]; for (int e head[u]; e ! -1; e nxt[e]) { int v to[e]; if (dist[v] ! -1) continue; dist[v] dist[u] 1; q[tl] v; } } return -1; }注意head数组要初始化为 -1这是前向星的命门忘了就是死循环或者越界。另外无向图记得addEdge(u,v)和addEdge(v,u)都要加旅游题的城市路网基本都是双向的单向的会特别注明从 A 到 B 有直达但反方向没有读到这种限制要多留个心眼。4.3 路径还原的最小改动如果题目不光问最小步数还要你把路线输出出来改动其实很小加一个pre数组在标记访问的时候顺便记下前驱。// 在 dist[nx][ny] dist[x][y] 1; 之后加一行 pre[nx * m ny] id;最后从终点往回倒推把路径存进栈里再正序输出。这一步很多人会忘记在起点直接等于终点的分支里也要输出一个点测试数据里经常藏着这种 input。5. 旅游题的四种常见变种与对应改法5.1 多源 BFS不确定从哪儿出发有时候题目会给出好几个WZK 可能出发的城市问你到某个终点的最省路线或者反过来同时求所有点到最近某个特殊点的距离。这时候把所有源点一次性入队dist全初始化为 0然后跑一次普通 BFS 就行。原理很好理解想象同时往水面丢好几颗石子波纹互相交汇的地方就是两个源点的势力范围边界。因为 BFS 是均匀扩散的谁先扩到就是谁的。这个技巧在求每个点到最近加油站的距离求每块陆地到最近的海这类题目里非常好用一次 BFS 解决比每个源点单独跑一遍快了不止一个数量级。实现上唯一要注意的是源点集合要去重如果输入里有重复的起点老老实实判一下dist是否已经是 0不然队列会白白膨胀。5.2 0-1 BFS当某些路不花代价旅游题很爱设计某条高速免费某段可以瞬移这种情节。边权变成 0 和 1 两种就不能用普通队列了得用双端队列。dequeint dq; fill(dist, dist MAXN, 0x3f3f3f3f); dist[s] 0; dq.push_front(s); while (!dq.empty()) { int u dq.front(); dq.pop_front(); for (int e head[u]; e ! -1; e nxt[e]) { int v to[e], w weight[e]; // w 只能是 0 或 1 if (dist[u] w dist[v]) { dist[v] dist[u] w; if (w 0) dq.push_front(v); else dq.push_back(v); } } }它成立的原因在于双端队列维护了一个大致有序的结构队首附近的距离值小队尾的大。代价 0 的转移不增加距离自然应该排在前面优先处理。这个结构保证了每个点第一次被真正确定时距离已经最小。一个常见误解是 0-1 BFS 里也要写vis跳过。其实不需要靠dist的松弛条件就够了——松弛不成立就不会入队逻辑自洽。如果你非要加vis必须保证加在弹出后并且只在第一次弹出时使用否则会漏掉更优的解。5.3 分层图与状态压缩附加维度怎么加题目如果限制最多可以免费 k 次状态就从u变成(u, c)其中c是已用次数。这就是分层图本质是把原来的图复制 k1 份第 c 层代表已用 c 次。int dist[MAXN][11]; // 第二维是已用次数k 通常很小 int q[MAXN * 11]; // 转移时 // 不用免费从 (u, c) 到 (v, c)代价 1 // 用免费从 (u, c) 到 (v, c1)代价 1次数这一维不算步数数组第二维只开 11写起来不费劲但状态总数翻了十倍队列容量必须跟着放大这一点极容易忘。至于必须收集若干物品那一类状态里塞一个二进制掩码2^m倍m 一般不超过 10 到 15。这时候再想用二维数组就不现实了得用mapvectorint, int或者把状态编码成u * (1m) mask这种一维整数。编码后的状态空间可能上百万务必先估内存再动手。5.4 带必经点的情形BFS 和状压的结合更狠的一种问法是走遍所有景点最少多少步。这时候状态是(当前位置, 已访问景点集合)转移是走到一个还没去过的景点并更新掩码。做法是先用 BFS 算出任意两个关键点起点、终点、所有景点之间的距离再用一个状压 DP 把这些距离串起来。这个套路值得记住因为它把一个大问题拆成了两步BFS 负责点对点最短路状压 DP 负责访问顺序。两件事都简单合起来就能解决一类看起来很难的题。前提是景点数量不多一般十个左右还能吃得住超过十五个就要另想办法了。6. 提交之后WA、TLE、MLE、RE 的排查顺序6.1 先怀疑边界再怀疑逻辑WA 的时候我的排查顺序永远是固定的先把数据范围里最小和最大的边界单独拎出来测一遍。最小边界包括起点等于终点答案是 0 还是 -1、地图只有一行或一列、全是障碍、终点点被围死。最大边界包括n 和 m 都取到上限、所有格子都能走此时队列会塞满所有点最容易爆容量、路径长度接近上限。这几组测完大部分 WA 的原因就露头了。然后才是逻辑。逻辑错误里最常见的三个方向数组写错有的是四方向写成八方向有的是dx和dy配错了对、访问判断漏掉某一维比如分层图里只判了u没判c、输出格式不对多组数据少输出了换行或者不可达时题面要求输出-1而你输出了0。6.2 TLE 的三种成因与卡常手段TLE 通常来自三类原因按概率从高到低排队列膨胀、重复清空、常数太大。队列膨胀就是前面说的标记位置错了先回去检查vis标记是不是在入队前。重复清空就是多组数据时memset了一个巨大的数组改用时间戳。常数太大则是std::queue或者vector的动态扩容造成的换成静态数组模拟队列。再往上一层还有几个卡常技巧我用得比较多把(x, y)压成一维整数减少访存把方向数组的循环展开成四段编译器开-O2一般也会做但关键题可以手动写把if (nx 0 || nx n || ny 0 || ny m)换成在边界外扩一圈哨兵把地图外围一圈全部标成障碍这样就不用判越界了省掉两次比较。最后这个哨兵技巧我特别推荐因为它同时能防住越界 RE。做法是读入地图时坐标从 1 开始把第 0 行、第 n1 行、第 0 列、第 m1 列全部设成不可走循环里就只剩一句if (g[nx][ny] #) continue;代码短了也快了。6.3 RE 与 MLE 的典型触发器RE 在 BFS 里几乎只有两个来源队列数组开小了或者数组下标算错了。队列开小了最隐蔽因为小数据全过大数据一交就炸。判断方法是把MAXS临时开大十倍试试如果过了那就是容量问题。下标算错通常是压缩状态时的编码冲突比如x * m y里 m 写成了 n或者没考虑 0 起始和 1 起始的区别。MLE 则多是局部数组开在栈上导致的。一个int dist[1005][1005]放在函数里就是 4MB加上几个类似的就超过默认栈限制了直接段错误。养成习惯大数组一律开全局全局变量在静态区不受栈大小限制。6.4 一个容易被忽略的点输入读入方式地图题里如果用scanf(%c)逐个读字符换行符会被当成一个格子的内容读进来整个地图错位一格然后你调一晚上都找不到问题。解决办法是用scanf(%s)按行读或者cin g[i][j]逐个读它会自动跳过空白或者读完整行再逐字符处理。我自己的习惯是字符地图一律用scanf(%s, g[i] 1)下标从 1 开始天然避开换行问题还顺便能用上前面的哨兵技巧。这一条看着不起眼但它救过的调试时间比任何算法优化都多。7. 对拍把我觉得对变成它确实对7.1 暴力怎么写当你的 BFS 交上去一直 WA 而你又看不出问题时最快的办法不是继续盯代码是写一个暴力程序。暴力不需要效率只需要绝对正确且容易验证。对于求最短步数的题暴力有几种写法。最朴素的是深搜枚举所有路径取最小值加上步数上限剪枝如果图很小可以用 Floyd 求全源最短路如果状态空间不大甚至可以直接做 BFS 但用set存状态虽然慢但逻辑简单到你不可能写错。暴力程序的价值在于它是另一个独立实现。同一个逻辑用两种方式写两边同时错的概率远低于一边错。我自己写暴力时故意用完全不同的数据结构就是为了避免复制粘贴同一个错误。7.2 造数据与对拍脚本数据生成器我一般用 Python 写因为随机数的控制比 C 顺手。import random n random.randint(1, 8) m random.randint(1, 8) print(n, m) grid [] for i in range(n): row .join(random.choice(..#) for _ in range(m)) grid.append(row) print(\n.join(grid)) sx, sy random.randint(0, n-1), random.randint(0, m-1) tx, ty random.randint(0, n-1), random.randint(0, m-1) print(sx, sy, tx, ty)注意生成器里要控制障碍比例全障碍或者全通路都测不出问题我一般让#占两成左右。另外起点和终点要允许重合这是最容易漏测的边界。对拍脚本用 shell 就行while true; do python3 gen.py in.txt ./bf out1.txt in.txt ./std out2.txt in.txt if ! diff -q out1.txt out2.txt /dev/null; then echo 发现差异输入已保存在 in.txt break fi done跑起来之后去泡杯茶回来看看是不是停在了某组数据上。停下来的那组输入就是你梦寐以求的反例直接拿去单步调试通常五分钟内就能定位。提示对拍时编译器一定要开-Wall -Wextra很多未初始化变量和越界隐患编译器会直接告诉你。我有一半的 RE 是被编译警告提前拦下来的。8. 我自己在这类题上的一些固定习惯写到最后分享几个我被坑出来、后来变成肌肉记忆的做法。第一写 BFS 前先在纸上画一个小例子手推一遍队列的变化。三五个节点的图画出每一层谁先入队谁后入队这个过程只要两分钟但能提前发现状态定义是不是漏了维度。我有太多次是敲完代码运行样例对了就交结果错在状态维度上回头改要重写一大半。第二dist数组的初始值我永远和不可达的语义绑定。网格题用 -1图论题用 0x3f3f3f3f绝不用 0。用 0 就意味着你得额外维护一个vis多一个数组就多一处出错的地方。第三队列容量宁可开大两个数量级也别刚好卡着上限。多占的那点内存换来的是一整晚的安心。真遇到内存卡得死的情况再回过头来做状态压缩。第四多组数据的题第一件事是把初始化写对再写算法。我见过太多人在算法上折腾一小时最后发现是上一组数据的head、tail没清零。这种错误事后看蠢得不行但当时就是看不见。第五不可达的输出格式一定回题面确认。有的题要求输出-1有的要求输出No solution有的要求输出0。这种细节失分最冤明明算法全对。这类某某去旅游求最短路线的题模板早就成熟了真正拉开差距的是你对状态空间的理解和对边界细节的敏感度。把上面几份骨架抄下来改改就能用但更值钱的是那几条排查顺序下次卡住的时候按着走一遍比盯着屏幕发呆有效得多。