# 转动的字节：题解

## 解法与贡献

采用出题人的反向逐字符 BFS：边标签变为额外结点标签，通过二进制稳定分组维护字符串顺序，并按前驱编号排列反向邻接。Codex（GPT-6）补充三级目标的证明、按实际规模分配存储和标准 C++17 实现。BFS 与稳定基数排序都是经典方法。

## 标签块与逐字符距离

把原边 $u\to v$ 的标签存成一个额外块 $e$ ，连接 $u\to e\to v$ .原结点也是块，因此共有 $n+m$ 个块。每个块保存其完整标签、已读取字符数、是否到达以及最先到达时的后继块。

从终点一沿反向边搜索，每次读取当前标签中从右往左的一个字符。读完块后进入其反向邻居。每一轮恰好读取一个字符，故 BFS 轮数就是已读的后缀长度。无需把每个字符单独建成图顶点；一个块内部的字符次序是固定的，可以仅保存一个下标。

所有标签非空，最短路径不含原图结点环；否则去掉环会减少字符数。这既保证答案可简单地重建，也说明较长的终点后缀永远不能帮助最短路径。

## 第二目标：在前面增加字符的稳定排序

反向读取并不意味着比较反向字符串。已经读到的字符始终表示其**正向顺序的后缀**；下一步把新字符加到这个后缀前面。

假设同一轮的状态已按它们代表的后缀字典序排列。下一轮的字符串形如 $cS$ ，其中 $c$ 为新字符、$S$ 为上一轮后缀。将所有新状态稳定地分为新字符零与新字符一两组：先处理零组，再处理一组；组内保留此前的状态顺序。它恰好按 $(c,S)$ 排序，因此也按新的正向后缀排序。初始只有终点标签的最后一个字符，归纳成立。

实现使用当前轮和下一轮各两个队列，共四个队列。不能把所有零字符边当作零费用边；每个字符都花费一轮。

## 第三目标：反向结点编号序列

把原结点 $v$ 的反向入边按原前驱编号 $u$ 升序排列。进入边块时，就可以把其原前驱编号视为加入反向编号序列；随后边块和结点块内部不再分叉。

考虑两条长度和完整字符串均相同的最优路径。如果它们经过某个相同原结点，各自从该结点到终点的部分都必须是该点的最短后缀；否则换成更短后缀会使完整路径更短。两段后缀长度因此相同。再由完整字符串相同，等长的终点后缀字符也相同。

现在从终点追踪两条路径，直到反向结点序列的第一个分叉。在分叉之前，各共同结点到达于相同字符层，且后缀相同。平行边若仍保持相同结点序列，它们在两条最优路径中也必须有相同长度和相同标签，否则无法保持相同的最短后缀。因而真正的第一次编号分叉发生在同一个状态，较小的前驱编号先入队。

此后，两条最终相同字符串在每个字符层都有相同的已读后缀，稳定分组不会颠倒它们的顺序。因此较小的反向编号序列先完成。若一个反向编号序列是另一个的真前缀，继续走至少再读一个非空标签，无法仍是相同长度的最优路径，所以不会破坏这一比较。

这也解释了为什么标签长短不同不会使第三目标失效：需要比较的最优路径到共同原结点的后缀距离相同，不能用较晚到达的同一结点参与平局。

## 为什么可以首次到达就标记

对于同一个块，较早轮次到达意味着更短的后缀。同轮到达时，上述队列顺序给出字典序更小的后缀；字符相同时，第三目标给出更小的反向编号序列。块内部剩余字符完全相同，且任何到该块的前半条路径都能接上这条更优后缀，因此后来到达被支配，可以舍弃。

对两个相同块后缀比较反向结点序列时，它们以同一个原结点结束；简单最短路径不会出现一条是真前缀的情形。因此将相同的前半路径接在后面不会颠倒编号序列顺序。

记录首次到达的 `From` 指针。从第一个完整读完标签的可选起点沿指针到一，依次输出各块的**原始正向标签**，再输出其中属于原图的结点编号。这就是三级目标最优答案；不能在刚进入起点块时提前结束，因为其剩余字符也计入长度与字典序。

## 邻接顺序与复杂度

为线性构建所需顺序，先把原边按起点分桶。按原起点编号从大到小扫描，把对应反向边插到链表头；最终每个原结点的前驱顺序就是升序。同一起终点间的平行边保持任意顺序都可以：字符不同会由稳定字符分组区分，字符相同则两项输出完全一样。

记 $L$ 为全部点标签与边标签的字符总数。每个块首次进入一次、每个块内字符处理一次、每条转换后的边检查一次，所以时间为 $O(n+m+L)$ ，空间为 $O(n+m+L)$ .本题每个标签长度至多五，可将时间与空间都写成 $O(n+m)$ ；实现为每块固定保存五个字符，不额外建立逐字符图。四个队列存块编号，并复用容量。

[参考程序](std.cpp)保留上述反向线性算法。另一种核验方式是先用 Dijkstra 求后缀距离，在最短路图上正向筛选最小字符串，再用匹配该字符串的可达性反向选择最小前驱；它将三个目标分开，但需要堆和额外的遍历，最坏时间增加为 $O((n+m)\log n+L)$ ，不作为本题的首选计算程序。