[你找的可能是这个（Jhonson算法）](https://www.cnblogs.com/gaochundong/p/johnson_algorithm.html)
qwq不过这是处理多源最短路，而且复杂度是$\Theta(nm)$的。
by 木木！ @ 2019-09-27 08:42:14
@[x义x](/space/show?uid=58567) 同一个节点进队$N+1$次说明有负环这个咋证啊qwq，似乎只有`SPFA`和`Stacked SPFA`作为`Bellman-Floyd`的队列优化才有这个性质吧（雾
by 木木！ @ 2019-09-27 08:44:10
@[Ametsuji_tachiaki](/space/show?uid=209807) 重载边权
听说要多建一个什么鬼图
by MZW_BG @ 2019-09-27 08:45:07
灯姐说得对
by 禰豆子 @ 2019-09-27 09:02:31
直接dijkstra多次入队是指数级的
by 142857cs @ 2019-09-27 09:04:47
那个重载边权是这样的:假设u->v 边权为w，dis是上一次最短路的结果，那么把u->v的边权改成w+dis[u]-dis[v]
by 142857cs @ 2019-09-27 09:09:25
@[木木！](/space/show?uid=49458) 哦好像确实是
by x义x @ 2019-09-27 09:17:17
Dij跑负权图我记得没错的话不是叫原始对偶吗
by 萌新蒟蒻 @ 2019-09-27 10:08:42
确实可以Johnson 但是您找到的文章能不能分享给我康康
by AnoonA @ 2019-09-28 16:09:34