$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

对AcWing 849. Dijkstra求最短路 I进行堆优化。

堆优化手写堆参照AcWing 839. 模拟堆
当然可以用优先队列，但是可惜优先队列不能控制元素个数（
所以优先队列中可能会出现 $m$ 个元素。
但是可以 AC 了。

由于这题是稀疏图，因此要采用链式前向星进行存储。
时间复杂度 $O(m~\log~n)$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i =1 ; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}