前言：最短路算法是我们非常熟悉的了。Dijkstra，SPFA等单源最短路算法是我们在竞赛中常用的算法。那么，假如题目要求的不是最短的呢？

Question（1）：给定一个图，求次短路。

对于次短路，很容易想到在比较的时候进行处理。

设dis(u)为原点s到u的最短路径，u为当前节点，v和u有边相连。

x = dis[v] + f[u][v];

则对于最短路：if(dis[u] > x) dis[u] = x;

而对于次短路：

if(dis[u]>x) dis2[u]=dis[u],dis[u]=x;

else if(dis2[u]>x) dis2[u]=x;

所以，对于次短路，只需加多一个数组即可。

那么，K短路呢？

Question（2）：给定一个图，求第K短路。

对于这个问题，可以用A*算法+Dijkstra解决。

先了解一下A*算法：

A*算法是一种典型的启发式搜索算法。定义：

h*(s)为状态s到目标的距离

h(s)为估价函数，状态s到目标距离的下界，即h(s)<=h*(s)

g(s)为到达状态s所需的代价

f(s)为s的启发函数。有f(s) = h(s) + g(s)。

那么，对于本题：h(s)就是源点到s的距离，g(s)为到终点t的实际距离。

如果能求出g，那么，当A*搜索了终点k次后，当前的h就为答案。

求函数g的方法：因为g(s)为到终点t的实际距离，所以，可以把原图的边反向后，把终点改成源点，跑一次Dijkstra，算出每一个点u到t的距离，就是所求的g。

附上求K短路的模板：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include