有向无权图中从s出发经3倍数边的最短路径方案修正

你的分层图构造思路完全正确，这是无权图上求解带模长度约束最短路径的标准分层图做法，只需要补充少量落地细节即可直接使用。

核心逻辑正确性 #

你设计的副本拆分和边构造规则，本质是把「到达当前节点时已走边数模3的余数」作为状态维度纳入图结构：

• 3个副本分别对应到达原节点时，路径长度模3的3种可能余数：你定义的v1对应余数0（走了3k条边）、v2对应余数1（走了3k+1条边）、v3对应余数2（走了3k+2条边）
• 你设计的3条跨副本边(u1,v2),(u2,v3),(u3,v1)，刚好对应「每走一条原图的边，路径长度加1，模3余数同步加1、满3归零」的状态转移，没有逻辑漏洞。

落地执行细节 #

直接按以下步骤跑算法即可得到正确结果：

• 初始化新图G'：对原图每个节点v生成3个副本，建议统一命名为v_0、v_1、v_2分别对应余数0、1、2，避免下标混淆（和你原来的v1、v2、v3只是命名差异，逻辑完全一致）
• 边构造沿用你的规则：对原图每条有向边u→v，在G'中添加3条权值为1的有向边：u_0→v_1、u_1→v_2、u_2→v_0
• 确定BFS起点：初始状态下在起点s处走了0条边，0模3为0，因此BFS从s_0出发，初始距离设为0
• 执行标准无权图BFS，遍历G'中所有可达节点并记录最短距离
• 结果读取：原图中节点u的答案，就是G'中u_0节点的最短距离；如果u_0不可达，说明不存在从s出发、边数为3的倍数到达u的路径。

正确性补充说明 #

这个构造的核心是保证了G'中的路径和原图中带余数约束的路径一一对应：G'中从s_0到u_r的长度为d的路径，等价于原图中从s到u存在一条长度为d的路径，且d mod 3 = r。由于BFS在无权图上首次到达节点时的距离就是最短路径长度，因此得到的结果天然满足「最短」要求，不需要额外处理环的绕路问题——即使存在长度为3的环，BFS也会优先找到更短的合法路径。

内容的提问来源于stack exchange，提问作者semicolon