堆优化-dijsktra模版

核心思想 – 贪心
1. dist表示每个点到源点的距离
2. 维护一个堆，开始时堆中只有源点，到自己的距离是0，每次从堆中取一个到源点距离最短的且没有确定最短
距离的点，将所有与该点相连且没有确定最短距离的点点最短路径更新，并放入堆中
2. 直到堆中没有元素

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 150010, M = 150010, INF = 0x3f3f3f3f;
int n, m;

int h[N], e[N], v[N], ne[N], cnt;

int dist[N];
bool st[N];

typedef pair<int, int> PII;


void add(int a, int b, int c) {
    e[cnt] = b, v[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
}

void dijsktra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;  // 源点可以改变

    priority_queue<PII, vector<PII>, greater<PII>> q;
    //st[1] = true;
    q.push({0, 1});

    while (!q.empty()) {
        auto t = q.top();
        q.pop();

        int ind = t.second, dis = t.first;
        if (st[ind]) continue;
        st[ind] = true;
        for (int i = h[ind]; ~i; i = ne[i]) {
            int j = e[i];
            if (!st[j] && dist[j] > v[i] + dis) {
                dist[j] = v[i] + dis;
                q.push({dist[j], j});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i++) {
        int a, b, v;
        cin >> a >> b >> v;
        add(a, b, v);
    }

    dijsktra();
    //for (int i = 1; i <= n; i++) cout << dist[i] << endl;
    if (dist[n] == INF) cout << "-1" << endl;
    else cout << dist[n] << endl;

    return 0;
}