K 站中转内最便宜的航班

记住这句，下面每一帧都在套它。

最多 2 次中转 = 路径最多 3 条边。先把起点 0 记成 0，其余记 ∞；准备做 3 轮松弛，每轮让路径“多走一条边”。

第 1 轮 · 边 0→1：用上一轮的 dist[0]=0 加票价 100 = 100，比原来的 ∞ 便宜 → 更新 dist[1]=100。

第 1 轮 · 边 0→2：用上一轮的 dist[0]=0 加票价 500 = 500，比原来的 ∞ 便宜 → 更新 dist[2]=500。

第 1 轮 · 边 1→2：上一轮还没到过 1（dist=∞），这条边暂时用不上，跳过。

第 1 轮 · 边 1→3：上一轮还没到过 1（dist=∞），这条边暂时用不上，跳过。

第 1 轮 · 边 2→4：上一轮还没到过 2（dist=∞），这条边暂时用不上，跳过。

第 1 轮 · 边 3→4：上一轮还没到过 3（dist=∞），这条边暂时用不上，跳过。

第 1 轮松弛完毕：此时的 dist 是“最多走 1 条边”能拿到的最便宜价。终点 4 这轮还到不了。

第 2 轮 · 边 0→1：dist[0]=0 加票价 100 = 100，不比现有的 100 便宜 → 不更新。

第 2 轮 · 边 0→2：dist[0]=0 加票价 500 = 500，不比现有的 500 便宜 → 不更新。

第 2 轮 · 边 1→2：用上一轮的 dist[1]=100 加票价 100 = 200，比原来的 500 便宜 → 更新 dist[2]=200。

第 2 轮 · 边 1→3：用上一轮的 dist[1]=100 加票价 100 = 200，比原来的 ∞ 便宜 → 更新 dist[3]=200。

第 2 轮 · 边 2→4：用上一轮的 dist[2]=500 加票价 200 = 700，比原来的 ∞ 便宜 → 更新 dist[4]=700。

第 2 轮 · 边 3→4：上一轮还没到过 3（dist=∞），这条边暂时用不上，跳过。

第 2 轮松弛完毕：此时的 dist 是“最多走 2 条边”能拿到的最便宜价。到终点 4 暂为 700。

第 3 轮 · 边 0→1：dist[0]=0 加票价 100 = 100，不比现有的 100 便宜 → 不更新。

第 3 轮 · 边 0→2：dist[0]=0 加票价 500 = 500，不比现有的 200 便宜 → 不更新。

第 3 轮 · 边 1→2：dist[1]=100 加票价 100 = 200，不比现有的 200 便宜 → 不更新。

第 3 轮 · 边 1→3：dist[1]=100 加票价 100 = 200，不比现有的 200 便宜 → 不更新。

第 3 轮 · 边 2→4：用上一轮的 dist[2]=200 加票价 200 = 400，比原来的 700 便宜 → 更新 dist[4]=400。

第 3 轮 · 边 3→4：用上一轮的 dist[3]=200 加票价 100 = 300，比原来的 400 便宜 → 更新 dist[4]=300。

第 3 轮松弛完毕：此时的 dist 是“最多走 3 条边”能拿到的最便宜价。到终点 4 暂为 300。

3 轮全部做完，每轮只让路径多一条边，自然卡住了“最多 2 次中转”。终点 4 的 dist = 300，就是答案。

边界先想清。

两个高频追问。