回文最短路径：双端BFS状态设计与AtCoder ABC394E详解

老实说第一次看到这个题号的时候我愣了一下。AT_abc394_e也就是 [ABC394E] Palindromic Shortest Path来自 AtCoder Beginner Contest 394 的 E 题。这类题最吸引人的地方在于它把“最短路”和“回文串”两个看似毫不相干的东西揉到了一起。你不能再无脑跑 Dijkstra也不能直接套 Floyd而是要从“回文串天生需要两端对称”这个直觉出发重新设计状态和转移。这篇文章我会完整讲清楚题目在问什么、为什么普通最短路失效、BFS 状态怎么设计、代码怎么写、有哪些坑以及再往深一层还能怎么想。不管是刚接触图论 BFS 的新手还是想刷 AtCoder 的选手都能从中拿到一套直接可用的思路。1. 题目到底在问什么回文约束如何改变最短路1.1 输入输出与数据规模题目给一个 N×N 的矩阵N 不超过 80。第 i 行第 j 列如果是一个小写字母 a~z表示存在一条从 i 到 j 的、带这个字母标签的有向边如果是字符 -表示没有这条边。注意这里的关键点这是一个有向图。即使第 i 行第 j 列和第 j 行第 i 列都有边它们也是两条独立的边标签还可能不一样。每条边的“长度”都是 1但我们要的不是普通最短路而是要求所有有序点对 (i, j) 之间最短的“回文路径”的长度。回文路径的意思是把这条路径上经过的所有边上的字母依次取出来连成一个字符串这个字符串正着读和倒着读是一样的。比如有一条路径 i → a → b → a → j边上的字母依次是 x, y, x那么整条路径就是回文的。输出是一个 N×N 的矩阵第 i 行第 j 列表示答案如果无解就输出 -1。数据规模 N≤80 是一个非常明确的信号O(N³) 级别甚至 O(N⁴) 级别的算法都可能卡着时限通过但这道题真正的难点不在常数而在状态设计。1.2 为什么不能直接跑 Dijkstra很多人一看到“最短路径”四个字下意识就掏出 Dijkstra 或者 Floyd。但这道题里回文这个约束彻底破坏了最短路的贪心结构。普通最短路里从起点到某个中间点的最短路径可以直接作为整体最短路径的前缀。但回文不一样一条回文路径的前缀和后缀必须镜像对应前半段的走向会限制后半段的走向。你不能只从起点往终点方向扩展因为路径的“后半段”是由终点往回看的。换句话说回文串的核心是对称对称意味着两端同时决定中间。最短路问题的单向扩展方式在这里天然不适用。此时出现了一个非常自然的直觉既然回文要两端对称那我们就让路径从两端同时长出来。每次在左边补一个字母 c右边也补一个字母 c这样字符串仍然保持回文。这就是这道题最核心的思维转换从“单端扩展”变成“双端扩展”。1.3 这题的考点和定位从算法训练的角度看这道题综合了三个东西图上的 BFS、区间 DP 式的“两端收缩”思想、以及带标签有向图的建图技巧。光会 BFS 模板不够你得意识到这里 BFS 的“状态”不是一个点而是一个点对光会字符串处理也不够你得把回文串的递归性质“两边各去掉一个相同字母后仍是回文”搬到图上。这道题的定位更像是一道思维题它没有考复杂的数据结构但考你能不能从题目条件里抽出正确的状态定义。AC 率低不是因为这题代码难写而是因为状态转移方向容易想反。2. 核心状态设计与转移方程推导2.1 把路径切成两端回文的递推本质假设存在一条从 u 到 v 的回文路径 P路径上的字符串是 s且长度大于等于 2。因为 s 是回文所以 s 的第一个字符和最后一个字符相等记为 c。把首尾字符都删掉中间剩下的字符串 s 仍然是从某个点 x 到某个点 y 的路径而且 s 本身还是回文。这里的关键是删掉首尾字符后起点变成了谁终点变成了谁如果原来路径是 u → ... → x --c-- ...? 需要小心。更准确的描述是一个从 u 到 v 的长度为 L 的回文路径左边第一条边是 u → p 且字母为 c右边最后一条边是 q → v 且字母也为 c那么从 p 到 q 之间存在一条长度为 L-2 的回文路径。反过来如果已经知道从 p 到 q 存在长度为 L-2 的回文路径并且存在一条边 u → p 标着 c一条边 q → v 也标着 c那么我们可以把这两条边“垫”到回文路径的两端得到一条从 u 到 v 的、长度为 L 的回文路径。这就是转移的核心规律在已确定的回文状态两端同时垫上一条字母相同的边得到新状态。2.2 状态定义与初始化定义 dist[a][b] 表示从 a 到 b 的最短回文路径长度。初始状态有两类。第一类dist[i][i] 0。因为空串是回文从某个点出发走 0 条边回到自己天然满足条件。这里可能有人会纠结“空串算不算回文”但按这题的输出约定如果对角线无解要输出 -1而标准答案里对角线都是 0所以空串就是答案。第二类对每一条边 i → j它本身就是一个长度为 1 的字符串单个字符一定是回文所以 dist[i][j] 可以初始化为 1。这里需要额外注意一个细节如果存在自环边 i → i理论上从 i 走到 i 的长度可以为 1但已经被长度 0 严格优于所以自环边在初始化时必须跳过。把所有初始状态都塞进队列BFS 就会帮我们按长度递增的顺序一层一层扩展。2.3 转移规则的来源为什么两边同时垫字符现在假设已经确定了从 a 到 b 有一条最短回文路径长度是 dist[a][b]。我们想构造更长的回文路径。为了保持回文性质新路径必须形如x --c-- a ... 回文路径 ... b --c-- y。也就是说新起点 x 必须满足存在一条边 x → a且边上字母为 c新终点 y 必须满足存在一条边 b → y边上字母也是 c。这里有两个方向需要特别留意x → a 是“指向 a 的入边”b → y 是“从 b 出发的出边”所以建图时不能只存正向边还必须存反向边。这是实现上最容易出错的地方。转移式写出来就是dist[x][y] dist[a][b] 2条件是 dist[a][b] 已知边 x → a 的字母和边 b → y 的字母相同。因为每次转移都在两端各加一条边长度严格增加 2所以这个过程天然适合 BFS。用队列维护待扩展的状态每个状态第一次被确定时就是最短距离。3. BFS 实现完整步骤与代码解读3.1 建图正向表和反向表缺一不可用邻接矩阵读入数据后我们要维护两类邻接表。一类是正向表 g[u]记录从 u 出发的所有边边结构是 (to, char)另一类是反向表 rg[v]记录所有到达 v 的边边结构是 (from, char)。为什么要反向表看转移条件就明白了扩展状态 (a, b) 时我们要找的是“以 a 为终点的边”和“以 b 为起点的边”。前者只能靠反向表快速枚举后者靠正向表快速枚举。在实现上我建议直接把边按字母分组存储也就是 g[u][c] 表示从 u 出发、字母为 c 的边的目标点集合rg[v][c] 表示到达 v 的、字母为 c 的边的来源点集合。这样做的好处不只是代码清晰扩展时可以直接避开字母不匹配的边省掉一层字符比较。后面讲复杂度时你就能看到这个优化多值钱。3.2 队列初始化与长度单调性初始化分两步。第一步把所有 (i, i) 入队dist[i][i] 0。第二步扫描所有边如果 i ! j 且矩阵位置不是 -就把 (i, j) 入队dist[i][j] 1。这里有一个非常容易踩的坑如果某条边已经存在但它的目标点对正好是某个已经初始化为更短长度的状态不能覆盖。具体来说对角线状态 dist[i][i] 0 永远不能被自环边更新成 1所以我一般直接在读入时跳过 i j 的情况。BFS 的队列为什么能保证第一次出队的状态就是最短的因为所有初始状态长度分别为 0 和 1每次扩展出的新状态长度都是当前长度 2。队列按入队顺序一批批处理长度小的状态一定先被扩展。即使队列里同时存在长度为 3 和长度为 5 的状态也不会出现某个点对先被一个更长的路径确定、后再被更短路径更新的情况。3.3 参考代码下面是完整 C 实现这个版本按字母分组存储边扩展时只遍历相同字母的边。#include bits/stdc.h using namespace std; const int MAXN 85; struct Edge { int to; }; vectorEdge g[MAXN][26], rg[MAXN][26]; int dist[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; memset(dist, -1, sizeof(dist)); queuepairint, int q; for (int i 0; i n; i) { dist[i][i] 0; q.push({i, i}); } for (int i 0; i n; i) { string s; cin s; for (int j 0; j n; j) { char c s[j]; if (c -) continue; if (i j) continue; int id c - a; g[i][id].push_back({j}); rg[j][id].push_back({i}); if (dist[i][j] -1) { dist[i][j] 1; q.push({i, j}); } } } while (!q.empty()) { auto [a, b] q.front(); q.pop(); int cur dist[a][b]; for (int id 0; id 26; id) { for (const auto e1 : rg[a][id]) { for (const auto e2 : g[b][id]) { int x e1.to; int y e2.to; if (dist[x][y] ! -1) continue; dist[x][y] cur 2; q.push({x, y}); } } } } for (int i 0; i n; i) { for (int j 0; j n; j) { if (j) cout ; cout dist[i][j]; } cout \n; } return 0; }如果你更习惯 Python也可以写出完全等价的结构只是要注意 Python 的循环常数偏大N80 时最好也用按字母分组的写法from collections import deque n int(input()) g [[[] for _ in range(26)] for _ in range(n)] rg [[[] for _ in range(26)] for _ in range(n)] dist [[-1] * n for _ in range(n)] q deque() for i in range(n): dist[i][i] 0 q.append((i, i)) for i in range(n): s input().strip() for j, ch in enumerate(s): if ch - or i j: continue cid ord(ch) - ord(a) g[i][cid].append(j) rg[j][cid].append(i) if dist[i][j] -1: dist[i][j] 1 q.append((i, j)) while q: a, b q.popleft() cur dist[a][b] for cid in range(26): for x in rg[a][cid]: for y in g[b][cid]: if dist[x][y] -1: dist[x][y] cur 2 q.append((x, y)) for i in range(n): print(*dist[i])代码结构并不复杂但每一步都有它存在的理由。尤其是边按字母分组那一步绝不是为了炫技而是为了实打实减少无效枚举。4. 复杂度分析与实测优化4.1 最坏复杂度为什么是 O(E²)如果不按字母分组直接对所有点对 (a, b) 扩展时各遍历一遍 rg[a] 和 g[b]那么总操作次数是Σ(a, b) indeg(a) × outdeg(b) (Σa indeg(a)) × (Σb outdeg(b)) E × E O(E²)E 最大是 N(N-1)N80 时约为 6320所以 E² 约等于 4×10⁷。这个量级用 C 写两秒内稳稳跑完。Python 如果直接写会很吃力但也不是完全不能过关键就看常数怎么省。4.2 按字母分组到底有没有用按字母分组后对于每个状态 (a, b)我们不再同时遍历所有反边和正边而是逐字母处理。对于字母 c只遍历 rg[a][c] 和 g[b][c]。设 cnt_c 表示边上字母为 c 的边数那么总操作次数变为Σ(a, b, c) cnt_rev[a][c] × cnt_fwd[b][c] Σc (Σa cnt_rev[a][c]) × (Σb cnt_fwd[b][c]) Σc cnt_c²如果 26 个字母分布均匀cnt_c ≈ 6320 / 26 ≈ 243那么 Σc cnt_c² ≈ 26 × 243²只有大约 150 万次操作比原来少了两个数量级。最坏情况是所有边都标同一个字母那么复杂度退化回 E²也就是 4×10⁷。但此时代码内部不再需要比较字符是否相等常数仍然比朴素双重循环小。4.3 几个容易忽略的性能细节第一队列里存点对可以存成两个 int不要为了图方便存结构体或者 string尤其是 Python 里推荐用两个 list 分别存 a 和 b牺牲一点可读性换速度。第二dist 数组用 int 存 -1 和长度不建议用很大的 INF。用 -1 的好处是判断未访问时直接比较输出时也直接输出 -1不需要额外转换。第三读入用 ios::sync_with_stdio(false) 和 cin.tie(nullptr)这个虽然是老生常谈但在 4×10⁷ 次操作的背景下输入输出优化能省下不少时间。Python 那边则建议用 sys.stdin 一次性读入而不是反复 input()。第四所有初始状态要一次性全部入队不要边读边扩展。因为 BFS 的正确性依赖队列按长度单调排列初始化顺序不会影响正确性但分开写容易漏状态。5. 常见错误与排查技巧5.1 自环把 dist[i][i] 覆盖成 1这是我见过最多人踩的坑。初始化时先设置了 dist[i][i] 0然后扫描邻接矩阵如果遇到 s[i][i] 是字母有的写法会顺手把 dist[i][i] 1 并入队导致答案变成 1。解决方式有两种。第一种最简单读入时直接 if (i j) continue。第二种是保留自环边但更新时只有新值小于旧值才更新。考虑到从 i 到 i 的空串就是回文长度 0 必然最优直接跳过自环没有任何信息损失。5.2 方向搞反导致样例都过不了扩展状态 (a, b) 时需要的是“终点是 a 的边”和“起点是 b 的边”。前者枚举 rg[a]后者枚举 g[b]。有相当一部分人会在初始化和扩展时把 g 和 rg 的用法写反结果整个 BFS 的方向完全乱掉。一个很实用的自检办法随便挑一条长度为 2 的回文路径比如 x → a 和 b → y 的字母都是 c那么从 a 到 b 的空串就能扩展出从 x 到 y 的 cc。手工推一遍这个流程如果方向反了推出来的路径是从 a 到 b 的而不是从 x 到 y 的一眼就能发现。5.3 为什么 dist[x][y] ! -1 时可以直接跳过这个问题问的人不少。有没有可能某个状态先被一条长路径更新后来又被一条短路径更新答案是不会。因为 BFS 队列中的状态按长度单调递增出队。当我们在处理长度为 cur 的状态时所有长度小于 cur 的状态都已经出队并扩展完毕。如果 dist[x][y] 已经被更新过那它一定是通过某个长度小于等于 cur 的状态扩展出来的长度不可能超过 cur 2。因此当前这条长度为 cur 2 的候选路径不可能更优直接跳过完全安全。这个性质正是“每个状态只入队一次”的正确性基础。明白这一点后你甚至可以进一步用数组标记代替队列判重但没必要dist -1 本身就是最好的标记。5.4 输出与 -1 的坑输出要求每一行之间的数字用空格隔开最后一个是 -1 时也要正常输出。这个没什么技术含量但容易在赶时间的时候把换行多打或者少打。建议把输出单独拎出来写一个循环不要和 BFS 混在一起。另外矩阵是对称读入的但答案不一定对称。因为图本身是有向图从 i 到 j 可能有回文路径从 j 到 i 可能没有。输出时千万不要想当然地复用对称值。6. 更进一步这类题还能怎么想6.1 把回文路径理解成双向扩展的字符串匹配从更高维度看这题本质上是在一个有向带标签图上寻找满足“正向字符串等于反向字符串”的路径。dist[a][b] 可以理解为两条字符串的匹配长度一条从 a 出发一条从 b 反向出发。每次扩展相当于让两条字符串同时往后各读一个相同字符。这样理解之后你会发现这题和自动机上的回文子串匹配是同一个思想。回文串的问题往往都可以转化为“两段字符串逐渐靠拢”的问题BFS 只是其中一种实现手段。如果题目改成求最长回文路径那么就要考虑图上的环问题性质就完全变了。这也是为什么这道题适合作为双端 BFS 类题目的入门题。6.2 单点对查询时的双向 BFS 剪枝技巧如果题目只问一个特定点对 (s, t) 的最短回文路径不需要求出全矩阵答案我们可以在上述全源 BFS 的基础上做双向剪枝。具体做法是从 (s, s) 和 (t, t) 两端同时开始扩展。每次选择一个方向扩展一层一旦发现某个状态从两端都被访问到就说明找到了一条回文路径。由于每次扩展长度增加 2最终拼接时如果两端长度分别为 L1 和 L2且某个公共状态被两端的路径覆盖那么总长度就是 L1 L2。这个剪枝在最坏情况下不会改变复杂度阶数但实际数据里往往能减少大量无效状态。我的经验是如果题目的输入矩阵非常稀疏双向扩展的效果会非常明显。6.3 和区间 DP / 马拉车思路的横向对比其实在想到 BFS 之前我第一反应是区间 DP。把这个图看作字符串的集合回文路径的判定天然适合“两端收缩”的区间模型。但区间 DP 要求枚举所有可能的起终点复杂度通常是 O(N³) 甚至更高在这题里状态总数 N² 加转移枚举就已经接近极限DP 并不占优势。马拉车的思路也有启发但马拉车依赖单个字符串的前缀信息在图上无法直接套用。真正与本题神似的反而是“两端同时向外扩展”的对称思想。理解了这一点以后遇到任何“带条件的路径存在性”问题都可以先问自己一句条件是否能被拆成两端同时满足的局部性质如果是BFS 状态很可能就是一个二元组。最后再分享一个我在实际排查中特别喜欢用的方法样例数据太弱自己手搓一个 N3 的全连接图给每条边编号把所有 dist 状态按长度分层打出来。如果一个长度为 3 的状态没被推出来大概率是反向表建错了如果一个长度为 4 的状态出现了但实际字符串不是回文大概率是扩展时字母判断写错了。这种小规模暴力验证比对着代码干瞪眼高效得多。做这类图上的双端 BFS调试的心法就一句话不要相信直觉让状态自己把路径讲出来。