给一个图，起点s、终点t、k，求起点到终点的第k短路。 基本思路： 首先反向图中求出终点 t 到其他所有点的距离（预处理优化）， 再从起点开始使用优先队列进行宽搜，用cnt记录到达终点的次数，当cnt==k时的路径长度即为所得。 搜索的方向用一个估价函数 f=g+h 来确定，其中g表示到当前点的路径长度，h表示当前点到终点的最短路径，即之前的预处理。 A*算法结合了启发式搜索

点击打开链接 分析：A*算法主要由是估价函数f(n)=g(n)+h(n);其中g(n)代表当前的实际代价。h(n)是估计代价。算法的效率直接取决于h(n)的评价性。h(n)的设计思想是无限靠近（极限）. 在本题中，g(n)代表从初始位置到当前x点所付出的代价。h(n)代表从当前x点到目标位置的估计代价。本题关键是怎样求h(n)，每个点到目标点t不一定联通。也不好估价， 巧妙之处是：从目标t到