别的我不知道，我只知道 queue 插入和删除是 O(1) 的
by liqingyang @ 2023-01-12 21:10:02
@[liqingyang](/user/272088) 啊啊啊，看来是我记错了（大哭
by skyfly886 @ 2023-01-12 21:12:12
@[skyfly886](/user/300737) $log(n)$ 不是二分查找和平衡树查找吗
by 0x1bf52 @ 2023-01-12 21:16:53
@[tl_xujiayi](/user/906320) 其实我发这个帖子的主要目的是想问一下，为什么我稍微更换了一下写法，就能提升那么多的时间效率
by skyfly886 @ 2023-01-12 21:27:59
@[skyfly886](/user/300737) 你时间复杂度很有**可能**是错的，比如说一个 DAG，$n$ 个点连向 $n+1$ 号点，然后成功更新了 $n$ 次，那么你的第一个写法就往 queue 里放了 $n$ 个点，然后 $n+1$ 有 $m$ 条出边，那么就会执行 $nm$ 次松弛。
有点类似 BFS 与 SPFA 的区别。
（没看题瞎糊的，可能锅）
by reveal @ 2023-01-12 21:34:16
@[reveal](/user/523491) 感谢感谢，蒟蒻再去研究一下
by skyfly886 @ 2023-01-12 21:41:15
@[skyfly886](/user/300737) 第一个G是map，第二个G是数组。map复杂度是 $\mathcal{O(\log n)}$ 的。
by yangwuqi @ 2023-01-22 21:57:29
@[yangwuqi](/user/530267) 真的诶，原来问题在这里，感谢大佬
by skyfly886 @ 2023-01-25 11:32:39