@[_Wolverine](/space/show?uid=120362) 堆优化力度很强
by hater @ 2019-05-13 20:14:52
强烈推荐 （加强版的都可以A）
by hater @ 2019-05-13 20:15:15
堆优化是很强，但堆优化学傻了也不是很好。。。不加优化的dijkstra在稠密图中可是线性的
by 142857cs @ 2019-05-13 20:20:32
不加优化的 $Dijkstra$ 是 $O(n^2)$ 的吧
by yurzhang @ 2019-05-13 20:22:47
@[yurzhang](/space/show?uid=126486) m是n^2级别不就关于m线性了？
by 142857cs @ 2019-05-13 20:42:50
@[142857cs](/space/show?uid=35760) 因为图论题目大多 $n$ 和 $m$ 同级所以说顺口了，没有优化的 $\text{Dijkstra}$ 应该是 $O(nm)$ 的，可能还没 $\text{SPFA}$ 快
by yurzhang @ 2019-05-14 00:03:25
@[yurzhang](/space/show?uid=126486) 没有优化的dijkstra是O(n^2)的，不是O(nm)
by 142857cs @ 2019-05-14 18:22:00
@[142857cs](/space/show?uid=35760) 可是这只能让你的 $\text{Dijkstra}$ 比 $\text{SPFA}$ 最劣复杂度好上那么一点，没有堆优化的 $\text{Dijkstra}$ 复杂度是错的，凭什么能过题？
by yurzhang @ 2019-05-14 18:28:55
@[yurzhang](/space/show?uid=126486) 可以出n=5000,m=20000000的最短路卡你堆优化
by 142857cs @ 2019-05-14 18:31:57
@[142857cs](/space/show?uid=35760) 可是我从来不写 $\text{Dijkstra}$ ，另外你的数据要怎么把边读进来？
by yurzhang @ 2019-05-14 18:33:50