A* 求 第 k 短路

最后总结一下流程，
首先建反向图用 SPFA 跑出来终点到各个点的最短路 dis[N]。
用 f[i] 作为优先队列的关键字来进行 A*。
这里 h[i] = dis[i];

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int M = 1e4 + 10;

int n, m, S, E, K, T;

struct node{
    int to, w, ne;
} e[M], re[M];  // 反向边跑 SPFA， 正向边跑 A*

int h[N], rh[N];
int idx;

void init(){
    idx = 0;
    memset(h, -1, sizeof(h));
    memset(rh, -1, sizeof(rh));
}

inline void add(int x, int y, int w){
    e[idx].to = y, e[idx].w = w, e[idx].ne = h[x], h[x] = idx;    // 正向
    re[idx].to = x, re[idx].w = w, re[idx].ne = rh[y], rh[y] = idx++; // 反向
}

int dis[N], vis[N];

// 求出终点到各点的最短长度 dis[i]
// 用这个长度来作为后面 A* 算法的启发式函数 h[i] 
void spfa(){
    memset(dis, INF, sizeof(dis));
    dis[E] = 0;         // 从终点开始
    queue q;
    q.push(E);
    vis[E] = 1;
    while(!q.empty()){
        int cnt = q.front();
        q.pop();
        vis[cnt] = 0;       // 遍历 cnt 的所有边
        for (int i = rh[cnt]; ~i; i = re[i].ne){    
            if(dis[re[i].to] > dis[cnt] + re[i].w){
                dis[re[i].to] = dis[cnt] + re[i].w;
                if(!vis[re[i].to]){
                    vis[re[i].to] = 1;
                    q.push(re[i].to);
                }
            }
        }
    }
}   

struct A{   // 优先队列默认弹出大的，所以这样重载
    int id, g, f;   // id 是点的号
    // 核心式子 ： f = g + h，这里 h(i) = dis[i];
    bool operator < (const A& b) const {
        if(f == b.f)
            return g > b.g;
        return f > b.f;
    }
};

int Astar(){
    int res = 0;
    if(S == E)  //判断相同点算不算最短路
        K++;
    if(dis[S] == INF)
        return -1;                  // 起点终点没有通路
    priority_queue q;            //优先队列 默认教大的值先出队列
    q.push(A{S, 0, 0 + dis[S]});
    while(!q.empty()){
        A cnt = q.top();
        q.pop();
        if(cnt.id == E){
            res++;
            if(res == K)    // 第 k 次到达就是结果
                return cnt.g;
        }
        for(int i = h[cnt.id]; ~i; i = e[i].ne){
            int a = e[i].to;               // 估计代价
            int b = cnt.g + e[i].w;         // 实际代价
            int c = b + dis[a];
            q.push(A{a, b, c});
        }
    }
    return -1;  // 没有第 k 短路
}

int main()
{
    while(~scanf("%d%d", &n, &m)){
        init();
        scanf("%d%d%d%d", &S, &E, &K, &T);
        for (int i = 1, x, y, w; i <= m; i++){
            scanf("%d%d%d", &x, &y, &w);
            add(x, y, w);
        }
        spfa();
        int ans = Astar();
        // cout << ans << endl;
        if(ans != -1 && ans <= T)
            printf("yareyaredawa\n");
        else
            printf("Whitesnake!\n");
    }
    return 0;
}