问题理解

我们有一个初始的无向连通图：

• $n$ 个节点，$m$ 条边
• 所有原始边的权值都是 $a$

然后进行特殊操作：

• 对于所有最短距离恰好为 $2a$ 的点对 $(u,v)$
• 在它们之间添加一条权值为 $b$ 的新边

最后问：从起点 $k$ 到所有节点的最短距离是多少？

关键观察

1. 新边的作用：新边实际上是在距离为 2 的节点对之间建立"捷径"

2. 三种移动方式：

   • 走 1 条原始边：花费 $a$
   • 走 2 条原始边：花费 $2a$
   • 走 1 条新边：花费 $b$

3. 重要结论：任何路径都可以看作是在原始图上走，偶尔用新边"跳过"2步

核心思路

方法：BFS + 距离分类

1. 先用BFS计算原图中的最短距离（按边数计算，不是权值）

   • $dist[i]$：从 $k$ 到 $i$ 在原图中的最短步数

2. 根据距离分类计算答案：

   • 如果 $dist[i]$ 是偶数：可以全部用新边，花费 = $\frac{dist[i]}{2} \times b$
   • 如果 $dist[i]$ 是奇数：最后一步必须用原始边，花费 = $\frac{dist[i]-1}{2} \times b + a$
   • 但是！还要考虑完全用原始边的情况：花费 = $dist[i] \times a$

3. 取最小值：

   ans[i] = min(上述两种方案，dist[i] × a)
   

算法步骤

1. 读入数据，建图
2. 从 $k$ 开始 BFS，计算每个点到 $k$ 的最短步数
3. 对于每个点 $i$：
   • 如果 $dist[i]$ 是偶数：candidate1 = (dist[i]/2) * b
   • 如果 $dist[i]$ 是奇数：candidate1 = ((dist[i]-1)/2) * b + a
   • candidate2 = dist[i] * a
   • ans[i] = min(candidate1, candidate2)
4. 输出结果

样例验证

输入：

5 5 1 3 2
1 2
2 3
3 4
4 5
3 1

BFS距离：[0,1,1,2,3]

计算：

• 点1：0
• 点2：min(1×3, 0×2+3) = 3
• 点3：min(1×3, 0×2+3) = 3
• 点4：min(2×3, 1×2+0) = min(6,2) = 2
• 点5：min(3×3, 1×2+3) = min(9,5) = 5

输出：[0,3,3,2,5] ✓

复杂度分析

• 时间复杂度：$O(n + m)$，一次BFS
• 空间复杂度：$O(n + m)$，存储图和距离数组

这种方法高效且易于实现，利用了新边的特殊性质来简化问题。