假定目标状态第一次出堆是 $(a,b)$ 其中 $a$ 是现在的总代价，$b$ 是预估代价。假定正确答案当前是 $(a',b')$ 因为其不为堆顶，所以 $a+b\le a'+b'$，而因为 $b'$ 不大于正确代价（假定为 $c$），所以 $a'+b'\le a'+c$ 所以 $a+b\le a'+c$，则 $(a,b)$ 必为答案。
by lsj2009 @ 2022-11-25 19:03:25
@[Rainsheeep](/user/666796)
by lsj2009 @ 2022-11-25 19:03:31