@a1b3c7d9 那题没必要线性吧...

对每一种长度的边分别开一个队列，表示被这种长度的边松弛的节点

你的意思是记录路径的最后一条边是什么，以此来给路径分类？

这个并没有维护单调性吧

由于 pop 的值是单调的，可知按边分类的每个队列都是单调的。

你们的意思是指算法流程是这样的：假设$a<b$，开两个队列$A,B$，每次从$A$队列取一个点$x$，并弹掉（如果$A$为空就从$B$中取），然后通过$x$的出边松弛其他节点，如果被松弛的节点$y$与$x$的边为$a$就加入队列$A$，否则加入队列$B$，然后这样做下去，两个队列无论如何都是单调的？

松弛的节点就直接加入队尾

还有这套理论没听说过"由于 pop 的值是单调的，可知按边分类的每个队列都是单调的。"，也不认为它是对的

pop是说你每次从 A, B 两个队列中pop较小的那个值，而且只有这种理解维护的才是一个优先队列啊 = =

前提的保证那个最小的元素加上a,b还会比队尾的元素大呀，所以就是这个是为什么呢？

要保证了这个性质，才有了pop的值是单调的呢

万分感谢，我终于明白了，此贴已结

感觉大家有点针对个人了，这个帖子本身没啥问题吧，（虽然回复稍微有点...），感觉帖子本身不足以被 downvote。