社区讨论

警示后人没过样例orWA on#12

2025/11/25 11:26P5905【模板】全源最短路（Johnson）参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 0 条
当前快照: 1 份
快照标识符: @mie0n3te
此快照首次捕获于: 2025/11/25 11:28
此快照最后确认于: 2025/11/25 13:40

如果你初始化dis数组为 $10^9$ ，最后处理最短路时不要处理 $10^9$ 。
由于加入了虚拟源点，那么现在图中共有 $n+1$ 个点，每个点最多能被更新 $n$ 次，超过 $n$ 次则有负环。

回复

共 0 条回复，欢迎继续交流。

正在加载回复...