给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。

注意： 每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数N和M。

接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。

最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。

输出格式

输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。

数据范围

1≤S,T≤N≤10001≤S,T≤N≤1000,

0≤M≤1050≤M≤105,

1≤K≤10001≤K≤1000,

1≤L≤1001≤L≤100

输入样例：

2 21 2 52 1 41 2 2

输出样例：

14

 

算法：A*

题解：预估函数是当前点到终点的距离，所以用spfa反方向跑一遍即可，利用优先队列，使当前总路径长度加上预估函数总和的最小值排序，求出第k短路即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define INF 0x3f3f3f3fconst int maxn = 1e5+7;struct node {    int v, l, f;    friend bool operator < (node a, node b) {        return a.l + a.f > b.l + b.f;    }};vector
         
          
            > g[maxn], gg[maxn];int dis[maxn];int vis[maxn];int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i<= m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); g[u].push_back(make_pair(v, w)); //正向建图 gg[v].push_back(make_pair(u, w)); //反向建图 } int s, t, k; scanf("%d %d %d", &s, &t, &k); for(int i = 1; i <= n; i++) { dis[i] = INF; } dis[t] = 0; queue
           
             q; q.push(t); while(!q.empty()) { //反向跑一遍spfa int u = q.front(); q.pop(); vis[u] = 0; int len = gg[u].size(); for(int i = 0; i < len; i++) { int v = gg[u][i].first; int w = gg[u][i].second; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } if(dis[s] == INF) { //判断是否连通 printf("-1\n"); return 0; } int cnt = 0; if(s == t) { //如果当前起点和终点重叠，则k多算一次 k++; } priority_queue
            
              pq; pq.push((node){s, 0, 0}); while(!pq.empty()) { //跑一遍A* node now = pq.top(); pq.pop(); if(now.v == t) { cnt++; if(cnt == k) { printf("%d\n", now.l); return 0; } } int u = now.v; int len = g[u].size(); for(int i = 0; i < len; i++) { int v = g[u][i].first; int w = g[u][i].second; pq.push((node){v, w + now.l, dis[v]}); } } printf("-1\n"); //没找到 return 0;}