比dij还麻烦有啥用Orz
by BuXiangJuanLe @ 2018-10-15 10:00:14
同上
by Enstein @ 2018-10-15 10:01:17
据说堆优化$\mathrm{SPFA}$能防止构造图卡它？
1. 跟用过`random_shuffle()`的$\mathrm{SPFA}$类似，它改变了节点的访问顺序
2. 如果有多条路从一个节点通往另一个节点，按照原来的（毒瘤数据想搞的）访问顺序，可能一条更比六条短，那个节点就会疯狂入队最终成为卡死$\mathrm{SPFA}$的罪魁祸首；而堆优化以后的$\mathrm{SPFA}$可以择优而行，必然先走最短的路，可以先更新出最小答案，从别的点再到这里的时候答案就比原来劣
（蒟蒻我的理解应该没错吧）
$\color{white}\text{验证码 FdwT}$
by PBCWZCC @ 2018-10-15 10:10:09
@[Izayoi](/space/show?uid=58197) 这上面两种做法都有
可是我怎么觉得它们差不多呢$\mathfrak{QAQ}$
by PBCWZCC @ 2018-10-15 10:11:41
我觉得你可以跑跑负环那道题试试
by Panthera_AFO @ 2018-10-15 10:15:13
加了堆优化的spfa不就是dij吗 我记得是这样子的哎
by foreverlasting @ 2018-10-15 10:37:03
同意楼上的观点，DJ的原理是每次把最近的点拿出来更新别的点 ，因为没有负权，所以那个点不可能再次被更新，所以不再入队。堆优SPFA应该是可以重复入队，这样虽然能跑负权，但仍比DJ慢
by Taduro @ 2018-10-15 10:43:09
## 比dij还麻烦有啥用
## 比dij还麻烦有啥用
by GNAQ @ 2018-10-15 10:49:06
那。。。
各位$\mathcal{DALAO}$去写$\mathrm{Dijkstra}$吧，别在嘲讽我了。。。
by PBCWZCC @ 2018-10-15 11:01:07
~~总不至于哪天负权卡普通SPFA吧~~
by PBCWZCC @ 2018-10-15 11:02:27