@[Graygoo](/user/535714)
没有问题罢
哪有后效性啊
只要没有负环,这跟全都是正权有啥区别
by Echidna @ 2022-05-14 21:29:28
@[liqingyang](/user/272088) 显然不行 下一个
by Echidna @ 2022-05-14 21:29:46
@[Echidna](/user/82284) 啊,复杂度会退化,但是正确性还对吧?~~可能是我弱智了~~
by liqingyang @ 2022-05-14 21:31:13
@[Echidna](/user/82284) ~~qs,我脑抽了~~但感觉是不是要多松弛几轮
by Graygoo @ 2022-05-14 21:31:28
@[liqingyang](/user/272088) 似乎没有这种魔改的dij
by Graygoo @ 2022-05-14 21:32:05
@[liqingyang](/user/272088)
复杂度能给妮妮姆退到指数级去
正确性也得寄
by Echidna @ 2022-05-14 21:32:37
@[Graygoo](/user/535714) 那这多松弛的几轮跟最短路计数也没任何关系啊
反正这东西只在最后一次更新的时候确定
by Echidna @ 2022-05-14 21:33:50
@[Graygoo](/user/535714) 其实说白了就是可以重复更新的dijkstra
因为当时不会SPFA,就想了个dijkstra应对负权,其实最劣复杂度还没SPFA优...不过也懒得学了,好像有些时候还是比SPFA快的...
by liqingyang @ 2022-05-14 21:34:46
@[liqingyang](/user/272088) 这种算法可以卡到指数级
by Echidna @ 2022-05-14 21:36:47
@[Echidna](/user/82284) 求大概说一下卡的数据,谢谢orz
by liqingyang @ 2022-05-14 21:44:21