无向图中最多使用1次指定边的最短路径求解问题

这个问题属于带次数约束的最短路径问题，用分层图建模可以完全复用标准Dijkstra逻辑，不需要修改算法核心，也不用额外设计复杂的边存储结构：

• 建立两层完全相同的原图：第一层对应「路径尚未使用过任何特殊边」的状态，第二层对应「路径已经使用过1次特殊边」的状态。
• 普通边处理：所有普通边在第一层内部、第二层内部各添加一次，无向边双向添加，权重和原边完全一致，保证两层内都可以正常走普通边。
• 特殊边处理：所有特殊边仅添加从第一层跨到第二层的双向边，不能在同层加特殊边，也不能从第二层往第一层加边，从逻辑上强制只能用最多一次特殊边：只要走了特殊边就会进入第二层，之后再也没有使用特殊边的入口。

• 节点编号映射：如果原图节点编号为1~n，可以直接把第一层节点编号保持为1~n，第二层节点编号设为n+1~2n，直接用普通邻接表存储所有边即可，不需要单独标记边的类型。
• 运行标准堆优化Dijkstra，起点设为第一层的起点s，最终答案取第一层终点t的最短距离、第二层终点t的最短距离二者的最小值，对应「完全不用特殊边」和「用了一次特殊边」两种情况的最优解。

总节点数为2n，总边数为2*普通边数 + 2*特殊边数，仍为线性量级，堆优化Dijkstra的时间复杂度为O(M + N log N)，和普通无约束最短路径的效率基本一致。

n = 原图节点数量
adj = [[] for _ in range(2 * n + 1)]  # 下标从1开始，1~n为第一层，n+1~2n为第二层

# 添加普通无向边u-v，权重w
def add_ordinary_edge(u, v, w):
    # 第一层加边
    adj[u].append((v, w))
    adj[v].append((u, w))
    # 第二层加边
    adj[u + n].append((v + n, w))
    adj[v + n].append((u + n, w))

# 添加特殊无向边u-v，权重w
def add_specific_edge(u, v, w):
    # 仅允许从第一层跨到第二层
    adj[u].append((v + n, w))
    adj[v].append((u + n, w))

# 调用标准Dijkstra计算从第一层起点s出发的所有最短距离
dist = dijkstra(adj, start=s)
# 最终答案取两种状态的最小值
ans = min(dist[t], dist[t + n])

如果你不想修改节点编号，也可以给Dijkstra的距离数组加一个状态维度：

• dist[u][0]表示到达节点u、尚未使用特殊边的最短距离
• dist[u][1]表示到达节点u、已经使用过1次特殊边的最短距离
  松弛的时候对应处理状态转移即可，逻辑和分层图完全等价：
• 当前状态为0时，走普通边仍转移到0状态，走特殊边转移到1状态
• 当前状态为1时，只能走普通边，仍转移到1状态

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