题目大意：给你一个有向图，并给你三个数s、t 和 k ，让你求从点 s 到 点 t 的第 k 短的路径。如果第 k 短路不存在，则输出“-1” ，否则，输出第 k 短路的长度。

        解题思路：这道题是一道简单的启发式搜索题目。而启发式搜索中A星算法是比较好理解的。A星算法中需要用到一个估价函数：f（n） = g（n）+ h（n）。其中，g（n）是当前量，h（n）是估计量，两者之和 f(n) 是估计值 。在这道题中，g（n）是从起点 s 到 点n 的已走距离，h（n）是从点n 到终点 t 的最短距离（dis[ n ]） 。每当我们走到一个点 tn 时 ，就计算出此时 tn 的g（tn） 、 h（tn）和 f（tn），把 tn 的这些信息压入一个队列，然后下一步选取队列中 f 值最小的节点作为下一步搜索的起点，如此反复，当我们第k次搜索到终点 t 时 ，这时g（t）的值就是我们要求的值。

        Ps：这里我们需要用到优先队列，并且要注意：因为必须离开 s 点再返回，所以，当 s == t 时 ，k ++ 。

请看代码：

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define mem(a , b) memset(a , b , sizeof(a))using namespace std ;inline void RD(int &a){ a = 0 ; char t ; do { t = getchar() ; } while (t < '0' || t > '9') ; a = t - '0' ; while ((t = getchar()) >= '0' && t <= '9') { a = a * 10 + t - '0' ; }}inline void OT(int a){ if(a >= 10) { OT(a / 10) ; } putchar(a % 10 + '0') ;}const int N = 1005 ;const int M = 1e5 + 5 ;const int INF = 0x7fffffff ;struct Edge{ int adj ; int d ; int next ;} E[M * 3] ;int head[N] ;int headN[N] ; // 反向图int dis[N] ;bool inq[N] ;int s , t , k ;int n , m ;int ce ;void chu(){ mem(head , - 1) ; mem(headN , -1) ; mem(inq , 0) ; ce = 0 ;}void init(){ chu() ; int i ; for(i = 0 ; i < m ; i ++) { int a , b , c ; scanf("%d%d%d" , &a , &b , &c) ; ce ++ ; E[ce].adj = b ; E[ce].d = c ; E[ce].next = head[a] ; head[a] = ce ; ce ++ ; E[ce].adj = a ; E[ce].d = c ; E[ce].next = headN[b] ; headN[b] = ce ; } scanf("%d%d%d" , &s , &t , &k) ;}queue
            
              q ;void spfa() // 计算 dis{ while (!q.empty()) q.pop() ; q.push(t) ; inq[t] = true ; int v ; while (!q.empty()) { v = q.front() ; q.pop() ; inq[v] = false ; int i ; for(i = headN[v] ; i != -1 ; i = E[i].next) { int tv = E[i].adj ; int td = E[i].d ; if(dis[v] + td < dis[tv]) { dis[tv] = dis[v] + td ; if(!inq[tv]) { q.push(tv) ; inq[tv] = true ; } } } }}struct F{ int Node ; int f ; int g ; int h ;};struct cmp{ bool operator () (F a , F b) { if(a.f == b.f) { return a.g > b.g ; } return a.f > b.f ; }} ;priority_queue
             
               , cmp> mq ;int SP() // A星 算法{ if(s == t) k ++ ; while (!mq.empty()) mq.pop() ; // 注意队列要清空 int cnt = 0 ; F u ; u.Node = s ; u.g = 0 ; u.h = dis[s] ; u.f = u.g + u.h ; mq.push(u) ; while (!mq.empty()) { F v = mq.top() ; if(v.Node == t) { cnt ++ ; if(cnt == k) { return v.g ; } } mq.pop() ; int i ; for(i = head[v.Node] ; i != -1 ; i = E[i].next) { int tv = E[i].adj ; int td = E[i].d ; F tmp ; tmp.Node = tv ; tmp.g = v.g + td ; tmp.h = dis[tv] ; tmp.f = tmp.g + tmp.h ; mq.push(tmp) ; } } return -1 ; // 注意：因为此图是有向图，所以K短路可能不存在！！！}void solve(){ int i ; for(i = 1 ; i <= n ; i ++) { dis[i] = INF ; } dis[t] = 0 ; spfa() ; if(dis[s] == INF) { puts("-1") ; return ; } else { printf("%d\n" , SP()) ; }}int main(){ while (scanf("%d%d" , &n , &m) != EOF) { init() ; solve() ; } return 0 ;}