在做最短路的题时我们不免会碰到许多求次短路的题，然而我们也能很快地想到解决的办法：

用dijkstra跑一遍最短路，当终点第二次被取出时就是次短路了。时间复杂度为O((N+M)logN)。实际上前面得乘个2.

那么根据OI的尿性，有了最优解问题，又有了次优解问题，接下来是什么？K优解！那么K短路怎么做？

仍然可以用上面的方法，用dijkstra不停地跑，直到终点被第k次取出时就是K短路。时间复杂度就是：O(K*(N+M)logN)。然而这种复杂度随便上网搜一道模板题都跑不过。

其实dijkstra可以看成加了优先队列的广度优先搜索。为了优化这种搜索，我们唯独可以在它的堆里面动点手脚。这时就要用到神奇的A*算法了。

根据设计估价函数的原则，其估计值f[x]不能大于其实际值，即无论K为多少时，f[x]都要小于等于x到终点的第K短路。通俗一点，设x到终点的所有path共同构成一个集合S：

\[ {\forall}path{\in}S,f[x]{\leq}lenth[path] \]

设x到终点的最短路为ShortestPath，上面的式子可以简化为：

\[ f[x]{\leq}ShortestPath \]

而这意味着我们直接令f[x]=ShortestPath就可以了！

所以我们首先预处理出所有点的预估值。具体操作是：建立反图，从终点开始跑出每个点的最短路的长度作为预估值。

然后我们每次只需要从堆里面取出dis[x]+f[x]最小的那个即可。当终点被第K次取出时就是K短路。

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 1001#define maxm 100001using namespace std;struct graph{    struct edge{        int to,dis,next;        edge(){}        edge(const int &_to,const int &_dis,const int &_next){ to=_to,dis=_dis,next=_next; }    }e[maxm];    int head[maxn],k;    inline void init(){ memset(head,-1,sizeof head); }    inline void add(const int &u,const int &v,const int &w){ e[k]=edge(v,w,head[u]); head[u]=k++; }}a,b;//a为正图，b为反图int f[maxn];bool vis[maxn];int n,m,s,t;struct set_elmt{    int id,dis;    set_elmt(){}    set_elmt(const int &_dis,const int &_id){ id=_id,dis=_dis; }    bool operator<(const set_elmt &x)const{ return dis>x.dis; }};//Dijkstra的优先级struct node{    int id,dis;    node(){}    node(const int &_dis,const int &_id){ id=_id,dis=_dis; }    bool operator<(const node &x)const{ return dis+f[id]>x.dis+f[x.id]; }};//A*的优先级inline int read(){    register int x(0),f(1); register char c(getchar());    while(c<'0'||'9'
        
          q;    q.push(set_elmt(0,t)),f[t]=0;        while(q.size()){        int u=q.top().id; q.pop();        if(vis[u]) continue; vis[u]=true;        for(register int i=b.head[u];~i;i=b.e[i].next){            int v=b.e[i].to;            if(f[v]>f[u]+b.e[i].dis) f[v]=f[u]+b.e[i].dis,q.push(set_elmt(f[v],v));        }    }}inline int astar(){    int K=read()+(s==t);//特判（起点=终点）的情况    priority_queue
         
           q; q.push(node(0,s)); while(q.size()){ int u=q.top().id,w=q.top().dis; q.pop(); if(u==t&&--K==0) return w; for(register int i=a.head[u];~i;i=a.e[i].next){ int v=a.e[i].to; q.push(node(w+a.e[i].dis,v)); } } return -1;}int main(){ a.init(),b.init(); n=read(),m=read(); for(register int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); a.add(u,v,w),b.add(v,u,w); } s=read(),t=read(); dijkstra(); printf("%d\n",astar()); return 0;}
         
        
       
      
     
    

* A * 的复杂度看似和普通的Dijkstra+Heap求K短路一样，都是O(K * (N+M)logN)，但实际上比它快很多。因为少搜了很多地方。