问：本题又 Dijkstra 解法吗？

P1462 通往奥格瑞玛的道路

bc2_cryeggy @ 2023-09-14 19:46:42

众所周知，Dijkstra 是 O(n^2) 的。所以如果本题使用 Dijkstra 的时间复杂度为 O(n^2 \text{ log } n)，会超时。但题解中有 Dijkstra 解法。

by ICU152_QWQ_IS8 @ 2023-09-14 19:47:57

虽然但是，dij有 m\log m 的做法啊

by ICU152_QWQ_IS8 @ 2023-09-14 19:48:40

@beautiful_chicken233

by hdkk @ 2023-09-14 19:49:22

@ISU152_YYDS m log m是啥做法啊，不是n log m吗

by ICU152_QWQ_IS8 @ 2023-09-14 19:50:00

@hdkk 堆优化的时间复杂度要是那么优秀就好了/kk

by hdkk @ 2023-09-14 19:51:15

@EasonLiang 6

by shinzanmono @ 2023-09-14 19:53:18

有没有一种可能，堆优化 dijkstra 是 O(m\log m) 的

by ICU152_QWQ_IS8 @ 2023-09-14 19:54:30

这年头有人连dij复杂度都背不掉了吗

by hdkk @ 2023-09-14 19:55:50

@ISU152_YYDS 搜了搜还真是，原来我记得一直是错的，谢谢大佬指正了

by EasonLiang @ 2023-09-14 20:01:55

@shinzanmono 所以堆优化的堆指的是优先队列吗..

by Coffee_zzz @ 2023-09-14 20:07:46

@EasonLiang 你愿意也可以手写堆实现。

| 下一页