求助，关于优先队列自定义比较函数

bsdsdb @ 2024-10-25 14:33:34

by Disjoint_cat @ 2024-10-25 14:37:38

@0x28202e202e29 你 dis 数组会改的啊，那不是出现后效性了吗

by bsdsdb @ 2024-10-25 14:39:40

@Disjoint_cat 但是不影响我取dis最短的数吧

by bsdsdb @ 2024-10-25 14:40:00

因为dis变短了都会重新入队

by Nuclear_Pasta @ 2024-10-25 14:42:45

@0x28202e202e29 Dijkstra 在运行过程中会修改尚未被 tag(扩展或标注确定)的节点的 dis 值，这会使左边的写法错误。右边的写法可以不出错，但出入站的元素数达到 \operatorname{O}(m)，得到实际复杂度 \operatorname{O}(m \log n)，这种写法在 \operatorname{O}(m) = \operatorname{O}(n ^2) 时比不用队列慢。

by Disjoint_cat @ 2024-10-25 14:50:05

@0x28202e202e29 不是哥们，那你堆里面都不满足堆性质了那它错了不是很正常吗（

by bsdsdb @ 2024-10-25 14:50:47

@Nuclear_Pasta 没太懂，我每次修改都是往小了改，每次取也是取dis小的，然后取了就tag，如果取到tag的直接跳过，好像没啥问题？

by bsdsdb @ 2024-10-25 14:52:40

@Disjoint_cat （思考）好像是的

by jimmy0926 @ 2024-10-25 14:55:00

@0x28202e202e29 往小了改就不满足堆性质，除非每次都 make_heap 复杂度飙升

by Nuclear_Pasta @ 2024-10-25 15:00:35

@jimmy0926 其实用手写堆就不用重构，只要改了对应节点，然后向上处理，或你实现任意点删除然后删一个加一个就可以 O(\log n) 修改。

by Moyou @ 2024-10-25 17:20:52

@Nuclear_Pasta 在堆里的元素个数也是 O(m) 个，所以应该是 O(m\log m)