堆优化dijkstra

需要前置知识朴素dijkstra

朴素dijk的算法中有一个瓶颈是选择出不在集合s中的离起点最近的点

在朴素的做法中，我们枚举整个d数组来找到这个点，其实可以考虑用小根堆优化

维护一个小根堆，其元素是一个结构体，成员有x，w两个，x代表点的编号，w代表d[x]

• 每次取出堆顶元素，如果已经在集合s中就抛去
• 如果不在集合s中，就加入之，然后尝试松弛
• 松弛成功的点y与松弛后的d[y]打包压入堆中

压堆操作的复杂度是log级别，所以堆优化dijk的时间复杂度是

O(NlogN)

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = N;
int n, m;

int head[N], to[M], w[M], nxt[M], idx;
inline void add(int x, int y, int z)
{
    to[++idx] = y;
    w[idx] = z;
    nxt[idx] = head[x];
    head[x] = idx;
}

struct node{
    int x, w;
    node(int x, int w): x(x), w(w){}; //带参构造函数
    friend bool operator > (const node &A, const node &B)
    {
        // 小根堆<greater>需要重载大于号
        return A.w > B.w;
    }
};

int d[N];
bool v[N];
void dijk(int s)
{
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    // 小根堆的定义
    priority_queue<node, vector<node>, greater<node> > Q;
    Q.push(node(s, 0));

    while (Q.size()) // 因为堆里可能存在s集合中的点，遇到要跳过，所以实际循环次数不确定
    {
        int x = Q.top().x;
        Q.pop(); // 注意，堆中的w只有排序的作用，不需要取出直接pop掉
        if (v[x]) // 遇到s中的点就跳过
            continue;
        v[x] = true; // 加入集合s
        for (int i = head[x]; i; i = nxt[i])
        {
            int y = to[i];
            if (d[y] > d[x] + w[i])
            {
                d[y] = d[x] + w[i];
                Q.push(node(y, d[y]));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }

    dijk(1);

    cout << (d[n] == d[0] ? -1 : d[n]) << endl;

    return 0;
}