为什么优先队列层层推进是错的Q=W=Q

P5022 [NOIP2018 提高组] 旅行

捞捞捞捞捞
by Pointer神教 @ 2021-10-14 19:47:35


@[Pointer神教](/user/382181) 确实我也没看懂题,一眼优先队列
by fanypcd @ 2021-10-19 21:32:14


![](https://cdn.luogu.com.cn/upload/pic/43845.png) 优先队列维护,答案是123456,然而正确答案显然为123645
by zhangyuzhe @ 2021-10-20 17:36:00


@[Pointer神教](https://www.luogu.com.cn/user/382181)
by zhangyuzhe @ 2021-10-20 17:36:30


设你现在走出来的路是一颗树,树根是起点,如果优先队列的话会使得你从某一棵子树跑到他的祖先再到另一颗子树。但是对于一个点来说,他被自己的父亲遍历只可能有一次。但是优先队列就不一定。比如说上边那位给的例子,你从2那颗子树走到三,实际上此时已经回不到2了
by Ranger_HoFr @ 2021-11-07 14:04:27


|