社区讨论
问题
P1144最短路计数参与者 2已保存回复 5
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mjwak1kd
- 此快照首次捕获于
- 2026/01/02 11:05 2 个月前
- 此快照最后确认于
- 2026/01/02 16:08 2 个月前
一开始看到题解加上方案数后却不加进队列感觉挺疑惑的，后面想想边权为 1，所以新更新到的最短路一定是最短的，进而可以想出用自己更新别人的点时自己一定更新完了，实际上就是 bfs，用最短路在加上边权后却不加进队列应该是既使用的最短路，但又夹杂了 bfs 的贪心。
所以几位题解既大材小用的使用的最短路，又还是用了 bfs 思想。
那么问题来了，如果边权不为 1，bfs 的贪心性质失效，直接在最短路统计答案还能对吗？
应该不行吧，一个点有可能先更新了它的出边的方案数，但是后来又被另一个点的最短路更新了，增加了方案数，然而它先更新的出边的方案数却没有被再次更新到。
这里问一下我的想法对吗？
那如果有这样一道题目，怎么解决它呢？（就是普通最短路加了个计数）
回复
共 5 条回复，欢迎继续交流。
正在加载回复...