> @[Bobh](/space/show?uid=59906) 骚年,$Dij$严格的$O(n\ log\ n)$,你体验过死掉的 加优化$SPFA$ 吗?
by arfa @ 2018-08-26 22:04:54
@[Bobh](/space/show?uid=59906) NOI2018归程了解一下
by Marser @ 2018-08-26 22:05:50
@[Bobh](/space/show?uid=59906) 使用**斐波那契堆**优化DJ
by hl666 @ 2018-08-26 22:06:47
您用spfa写写noi2018d1t1试试？
by newbie314159 @ 2018-08-26 22:08:47
@[hl666](/space/show?uid=41698) 请问斐波那契堆优化的dij是最快的吗？
by Bobh @ 2018-08-26 22:08:54
@[newbie314159](/space/show?uid=54979) 我的意思是dij应该比spfa要快，但为什么在这题中dij比spfa慢
by Bobh @ 2018-08-26 22:10:21
@[arfa](/space/show?uid=77760) dij用binary-heap是 $O(N+M)\log{N}$ 的，即使是fibo堆也是 $O(M+N\log{N})$ 的，稠密图 $M$ 能到 $N^2$，怎么就严格 $O(N\log{N})$ 了？
by SeKong @ 2018-08-26 22:11:06
@[Bobh](/space/show?uid=59906) 谁说一定要快了？
dij可以比spfa慢，但spfa卡起来可以到O(nm)
by newbie314159 @ 2018-08-26 22:12:38
> @[Skqliao](/space/show?uid=38018) 惊现网络流第一巨佬,日常膜拜。刚才的是失误,敬请原谅。~~不过斐波那契堆才好用~~
by arfa @ 2018-08-26 22:13:10
@[Bobh](/space/show?uid=59906) ~~我也没写过也不清楚呵~~
这个自行百度吧，据说斐波那契堆的复杂度是**均摊$O(1)$**的
by hl666 @ 2018-08-26 22:15:25