关于一种卡Dijkstra的方法
  • 板块学术版
  • 楼主yhylivedream
  • 当前回复13
  • 已保存回复13
  • 发布时间2024/5/11 19:52
  • 上次更新2024/5/11 21:51:29
查看原帖
关于一种卡Dijkstra的方法
778022
yhylivedream楼主2024/5/11 19:52

没有堆优化的 Dijkstra 时间复杂度是 O(n2+m)O(n^2+m) 的,而堆优化的 Dijkstra 时间复杂度是 O((n+m)log⁡n)O((n + m) \log n),那么是否可以构造一张点数为 n≥105n\ge10^5 以卡掉没有堆优化的,边数 m≥108m\ge10^8 (边数可以不给出自己构造)卡掉有堆优化的。

2024/5/11 19:52
加载中...