跑堆优化$dijkstra$模板题比$std::priority$_$queue$实现快了一倍左右

但是太麻烦了 不建议使用(

#include <cstring>
#include <cstdio>

const int N = 1.5e5 + 5, INF = 0x3f3f3f3f;

int e[N], ne[N], h[N], w[N], idx;
int hp[N], ph[N];
int in_heap[N];
int heap_idx, heap_size;
int dis[N];
bool vis[N];
int n, m, u, v, d;
struct PII {
    int x, y;
    bool operator< (const PII &p) {
        if (x != p.x) return x < p.x;
        return y < p.y;
    }
}heap[N];

void insert(int u, int v, int d) {
    e[idx] = v;
    w[idx] = d;
    ne[idx] = h[u];
    h[u] = idx++;
}

inline void swap(int &a, int &b) {
    a ^= b ^= a ^= b;
}

inline void swap(PII &a, PII &b) {
    PII t = b;
    b = a;
    a = t;
}

inline void heap_swap(int a, int b) {
    swap(heap[a], heap[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
}

void up(int u) {
    while (u >> 1 && heap[u] < heap[u >> 1])
        heap_swap(u, u >> 1), u >>= 1;
}

void down(int u) {
    int t = u;
    if (u << 1 <= heap_size && heap[u << 1] < heap[t]) t = u << 1;
    if ((u << 1 | 1) <= heap_size && heap[u << 1 | 1] < heap[t]) t = u << 1 | 1;
    if (u != t) heap_swap(t, u), down(t);
}

void modify(int u) {
    if (!in_heap[u]) {
        hp[++heap_size] = ++heap_idx;
        ph[heap_idx] = heap_size;
        heap[heap_size] = {dis[u], u};
        in_heap[u] = heap_idx;
        up(heap_size);
    }
    else {
        int k = ph[in_heap[u]];
        heap[k] = {dis[u], u};
        up(k);
    }
}

void dijkstra(int st) {
    memset(dis, 0x3f, sizeof dis);
    dis[st] = 0;
    modify(st);

    while (heap_size) {
        auto tt = heap[1];
        heap_swap(1, heap_size--);
        down(1);

        int t = tt.y;
        if (vis[t]) continue;
        vis[t] = true;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) {
                dis[j] = dis[t] + w[i];
                modify(j);
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d", &u, &v, &d);
        insert(u, v, d);
    }
    dijkstra(1);
    int res = dis[n];
    if (res == INF) res = -1;
    printf("%d\n", res);
    return 0;
}