思路解析 问题本质 从节点 1 到节点 n，求次短简单路径（不重复经过节点）。 关键观察 设最短路径为 P₁，次短路径为 P₂。由于 P₂ ≠ P₁，P₂ 必然至少缺少 P₁ 上的一条边。 算法：枚举删边 1. 先跑一次 Dijkstra，找到最短路径，记录路径上所有边 2. 依次删除最短路径上的每条边，每次重新跑 Dijkstra 3. 所有重跑结果中的最小值即为次短路径 正确性证明 * P₂ 不使用 P₁ 上的某条边 (u,v) * 当我们删掉 (u,v) 后，Dijkstra 找到的最短路 ≤ P₂（因为 P₂ 仍然有效） * 取所有删边方案的最小值，恰好就是次短路径 复杂度 * 最短路径最多 n-1 条边，每次删边跑 O(n²) 的 Dijkstra * 总复杂度 O(n³)，对 n ≤ 200 绰绰有余 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注意事项 * 自环需要跳过（对最短路无贡献） * 如果有多条最短路径，删掉其中一条的某条边后，另一条最短路径仍然存在，因此答案等于最短路径长度，符合题目要求