问题描述：解决边权为正的有向图两点之间非严格第 $k$ 短路径的长度。

$A^*$优化算法

采用Dijkstra最短路思想，每次扩展最短的路径，第 $k$ 次到达终点时的路径长度即为第 $k$ 短路的长度。

由于算法相当于同时进行 $k$ 次单元最短路，时间和空间都可能会超限，因此 预处理每个点到终点的最短距离作为估价函数，利用 $A^*$ 算法优化。

复杂度为 $O(nk\log n)$。

#include<bits/stdc++.h>

#define pii pair<int,int>
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e3 + 10, M = 1e5 + 10;

struct A_Star {
    int n, m, S, T, K;
    int head[N], ver[M << 1], edge[M << 1], Next[M << 1], tot;
    int rh[N], rv[M << 1], re[M << 1], rn[M << 1], rt;
    int f[N], v[N];

    inline void add(int x, int y, int z) {
        ver[++tot] = y;
        edge[tot] = z;
        Next[tot] = head[x];
        head[x] = tot;
    }

    inline void add_r(int x, int y, int z) {
        rv[++rt] = y;
        re[rt] = z;
        rn[rt] = rh[x];
        rh[x] = rt;
    }

    inline void dijkstra() {
        memset(f, 0x3f, sizeof(int) * (n + 1));
        memset(v, 0, sizeof(int) * (n + 1));
        priority_queue<pii > q;
        f[T] = 0;
        q.push({0, T});
        while (!q.empty()) {
            int x = q.top().second;
            q.pop();
            if (v[x])continue;
            v[x] = 1;
            for (int i = rh[x]; i; i = rn[i]) {
                int y = rv[i], z = re[i];
                if (f[y] > f[x] + z)f[y] = f[x] + z, q.push({-f[y], y});
            }
        }
    }

    inline void init() {
        tot = rt = 0;
        memset(head, 0, sizeof(int) * (n + 1));
        memset(rh, 0, sizeof(int) * (n + 1));
    }

    inline int solve() {
        n = qr(), m = qr(), init();
        for (int i = 1; i <= m; i++) {
            int x = qr(), y = qr(), z = qr();
            add(x, y, z), add_r(y, x, z);
        }
        S = qr(), T = qr(), K = qr();
        if (S == T)K++;//路径至少包含一条边
        dijkstra();
        if (f[S] == 0x3f3f3f3f)return -1;
        memset(v, 0, sizeof(int) * (n + 1));
        priority_queue<pair<int, pii>> q;
        q.push({-f[S], {0, S}});
        while (!q.empty()) {
            int x = q.top().second.second, d = q.top().second.first;
            q.pop();
            if (++v[x] == K && x == T)return d;
            for (int i = head[x]; i; i = Next[i])
                q.push({-(d + edge[i] + f[ver[i]]), {d + edge[i], ver[i]}});
        }
        return -1;
    }
} A;

int main() {
    printf("%d\n", A.solve());
    return 0;
}

可持久化可并堆优化算法

即便利用 $A^*$ 算法，还是可能被一些特殊数据卡成内存超限，这就需要采用可持久化左偏树进行优化。可持久化左偏树相较于左偏树，更适应于合并两个堆后还要保留原堆的情形。

首先建反图，从终点跑一遍最短路，求出每个可达的点到终点的最短路 $d$ ，然后找出从终点出发的最短路径生成树。

对于原图上的某一个点 $x$ ，如果该点到终点是可达的，那么遍历从该点出发经过每一条非树边到达的到终点可达的点 $y$ ，会有 $\Delta e=e_{x,y}+d_y-d_x$ 即相比于从点 $x$ 出发到达终点的最短路径，从 $x$ 出发经过点 $y$ 到达终点的最短路径长 $\Delta e$。将点 $x$ 的所有 $\Delta e$ 和 $y$ 存放在点 $x$ 对应的堆中。最后，将最短路径生成树中的每个点按深度有小到大顺序一次将每个点的父节点的堆中的元素合并到该节点中。

这样，对于点 $x$ 的堆中的堆顶元素，表示从点 $x$ 出发经一条与之相连的非树边后到达终点的最短路径。

从起点开始每次选进行类似 Dijkstra 算法的操作，建一个优先队列，初始状态将起点 $S$ 对应的左偏树堆顶的位置 $rt[S]$ 和 次短路长度 $d_S+\Delta e$ 放到优先队列中。每次取优先队列中最短的路径，然后对于该路径，找到可能的次短路径放到优先队列中。可能的次短路径为当前的取出的元素对应于左偏树节点 $y$ 的两个子节点，即从当前节点 $x$ 出发经非树边到达终点的所有最短路径中比经非树边到达 $y$ 对应在原图上的节点后到达终点的路径长的最短的两个路径，或者是 $y$ 的堆顶的元素，即 $y$ 对应在原图的点经与之相连的一条非树边后到达终点的最短的路径。

这样相较于未优化的 $A^*$ 算法，本质上是对每个节点上又加了一个优先队列，这样可以只把比当前路径短的所有可能的次短路径加入优先队列，而不是将所有可能结果加入优先队列，大大的优化了时间和空间复杂度。

#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e3 + 10, M = 1e5 + 10;

struct Leftist_Tree {
    int tot, rt[N];
    struct node {
        int dis, lc, rc, x, val;
    } t[N * 45];

    Leftist_Tree() { t[0].dis = -1; }

    inline int merge(int x, int y) {
        if (!x || !y)return x | y;
        if (t[x].val > t[y].val)swap(x, y);
        int p = ++tot;
        t[p] = t[x], t[p].rc = merge(t[x].rc, y);
        if (t[t[p].lc].dis < t[t[p].rc].dis)swap(t[p].lc, t[p].rc);
        t[p].dis = t[t[p].rc].dis + 1;
        return p;
    }

    inline void insert(int &p, int x, int v) {
        ++tot, t[tot] = {0, 0, 0, x, v};
        p = merge(p, tot);
    }
} L;

struct Kth_Path {
    int n, m, S, T, K;
    int head[N], ver[M], edge[M], Next[M], tot;
    int rh[N], rv[M], re[M], rn[M], rt;
    int d[N], fa[N];
    bool v[N], vis[N], ot[M];

    inline void add(int x, int y, int z) {
        ver[++tot] = y;
        edge[tot] = z;
        Next[tot] = head[x];
        head[x] = tot;
    }

    inline void add_r(int x, int y, int z) {
        rv[++rt] = y;
        re[rt] = z;
        rn[rt] = rh[x];
        rh[x] = rt;
    }

    struct node {
        int x, v;

        inline bool operator<(node a) const {
            return v > a.v;
        }
    };

    inline void dijkstra() {
        memset(d, 0x3f, sizeof(int) * (n + 1));
        memset(vis, false, sizeof(bool) * (n + 1));
        priority_queue<node> q;
        d[T] = 0;
        q.push({T, 0});
        while (!q.empty()) {
            int x = q.top().x;
            q.pop();
            if (vis[x])continue;
            vis[x] = true;
            for (int i = rh[x]; i; i = rn[i]) {
                int y = rv[i], z = re[i];
                if (d[y] > d[x] + z)d[y] = d[x] + z, q.push({y, d[y]});
            }
        }
    }

    inline void init() {
        tot = rt = 0;
        memset(head, 0, sizeof(int) * (n + 1));
        memset(rh, 0, sizeof(int) * (n + 1));
    }

    inline void bfs1() {
        queue<int> q;
        memset(ot, false, sizeof(bool) * (m + 1));
        memset(v, false, sizeof(bool) * (n + 1));
        v[T] = true, q.push(T);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i = rh[x]; i; i = rn[i]) {
                int y = rv[i], z = re[i];
                if (v[y] || d[y] != d[x] + z)continue;
                fa[y] = x, v[y] = ot[i] = true, q.push(y);
            }
        }
    }

    inline void bfs2() {
        queue<int> q;
        memset(v, false, sizeof(bool) * (n + 1));
        v[T] = true, q.push(T);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (fa[x])L.rt[x] = L.merge(L.rt[x], L.rt[fa[x]]);
            for (int i = rh[x]; i; i = rn[i])
                if (ot[i] && !v[rv[i]])v[rv[i]] = true, q.push(rv[i]);
        }
    }

    inline int solve() {
        n = qr(), m = qr(), init();
        for (int i = 1; i <= m; i++) {
            int x = qr(), y = qr(), z = qr();
            add(x, y, z), add_r(y, x, z);
        }
        S = qr(), T = qr(), K = qr();
        if (S == T)K++;
        dijkstra();
        if (!vis[S])return -1;
        if (K == 1)return d[S];
        bfs1();
        for (int x = 1; x <= n; x++) {
            if (!vis[x])continue;
            for (int i = head[x]; i; i = Next[i])
                if (!ot[i] && vis[ver[i]])
                    L.insert(L.rt[x], ver[i], d[ver[i]] + edge[i] - d[x]);
        }
        bfs2();
        priority_queue<node> q;
        if (L.rt[S])q.push({L.rt[S], d[S] + L.t[L.rt[S]].val});
        K--;
        while (!q.empty()) {
            node t = q.top();
            q.pop();
            if (!--K)return t.v;
            if (L.t[t.x].lc)q.push({L.t[t.x].lc, t.v - L.t[t.x].val + L.t[L.t[t.x].lc].val});
            if (L.t[t.x].rc)q.push({L.t[t.x].rc, t.v - L.t[t.x].val + L.t[L.t[t.x].rc].val});
            if (L.rt[L.t[t.x].x])q.push({L.rt[L.t[t.x].x], t.v + L.t[L.rt[L.t[t.x].x]].val});
        }
        return -1;
    }
} K;

int main() {
    printf("%d\n", K.solve());
    return 0;
}