问个问题

P1342 请柬

sansesantongshun @ 2024-02-16 10:56:08


by JOKER_chu @ 2024-02-16 11:05:52

SPFA 是 O(n log n)

dijkstra 是 O(n)


by JOKER_chu @ 2024-02-16 11:06:25

n 是点数


by JOKER_chu @ 2024-02-16 11:07:51

但对于这题好像不对啊


by HarmonicQuadrilatera @ 2024-02-16 11:17:19

@chuxm 您在说什么啊。

SPFA 是 O(nm) 的,但是在没有特意构造数据卡的情况下跑得很优秀。

Dij 是 O(n\log m)(二叉堆优化)O(m+n\log n)(更高级的优先队列优化)。


by JOKER_chu @ 2024-02-16 11:23:09

@HarmonicQuadrilatera

妈的,脑抽了,我的问题,那个是排序和插入


by JOKER_chu @ 2024-02-16 11:24:31

图上 SPFA 老师死活不讲,现在只会 Dijkstra 了


by JOKER_chu @ 2024-02-16 11:25:09

只记得 SPFA 比 Dijstra 跑的慢了


by sansesantongshun @ 2024-02-24 13:39:45

@HarmonicQuadrilatera Dij是 O(mlogn)


by HarmonicQuadrilatera @ 2024-02-24 17:15:17

@sansesantongshun 是(艹手滑打错了抱歉抱歉)


|