相信很多人都会求最短路,那么怎么求第k短路呢?我们可以直接爆搜,但是这样效率是很低的,这时我们可以用A*算法来解决这个问题。
令g[x]为当前的花费在这个问题里即为从1到x的路径长度,h[x]为估价函数在这里我们定为从x到n的距离是个不错的选择。然后我们设f[x]=g[x]+h[x]为x这点的估值。然后我们按f[x]排序,每次找f[x]最小的点进行扩展。
其中h[x]是可以预处理的,只需将边反向,然后从结束点跑一遍最短路即可。
具体代码及例题请点这里BZOJ1975: [Sdoi2010]魔法猪学院。
做题全靠自行脑补
17128884 99hgz 2449 Accepted 20372K 454MS C++ 2219B 2017-07-03 08:40:48
顺便求个证明什么的
还有a*求kth path是可以被卡掉的?
首先k短路的实质是暴力,
暴力你证明正确性的话比较强的。
还有A*是玄学时间空间的,
如果你想卡A*属于丧心病狂谢谢,
k短路暂时没有更好的求法了(呵呵
BZOJ上有一题就卡了A*基本所有人都打表。
谢谢