关于次短路

每个状态第一次出队,就是初始状态到它的最小代价。事实上,每个状态第 k 次出队,就是初始状态到它的第 k 小代价。(由数学归纳法)
并且每个状态的第 k 小代价,必是由某一个出队 k-1 次的状态扩展得到的。
故控制每个节点出队不超过 2 次, n 号节点第 2 次出队时的代价就是次短路。
一个注意点:每个节点最多扩展一次,入队一次,出队两次。
https://www.luogu.org/blog/107935/qian-tan-astar

岂能尽如人意,但求无愧我心
原文地址:https://www.cnblogs.com/Zforw/p/10888087.html