python/TangDou/AcWing/AStar/178_左偏树优化.cpp

#include <bits/stdc++.h>

using namespace std;
/*
可持久化可并堆优化算法

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

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

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

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

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

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

此种写法的效率极高，　16ms,大约是A*的10倍左右的性能，但因为现在功力有限，无法读懂，待我功力上长后，再来研究！

2022-10-11　黄海
*/

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 head);
        memset(rh, 0, sizeof rh);
    }

    inline void bfs1() {
        queue<int> q;
        memset(ot, false, sizeof ot);
        memset(v, false, sizeof v);
        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 v);
        v[T] = true, q.push(T);
        while (q.size()) {
            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() {
        cin >> n >> m;
        init();
        for (int i = 1; i <= m; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            add(x, y, z), add_r(y, x, z);
        }
        cin >> S >> T >> K;

        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.size()) {
            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() {
    //加快读入
    cin.tie(0), ios::sync_with_stdio(false);
    printf("%d\n", K.solve());
    return 0;
}