Dijkstra2(堆优化版)c++

在朴素版的Dijkstra中，找最小值的那步复杂度非常高，我们可以通过小根堆（堆头是最小值）找到最小值，降低复杂度。

流程及讲解

因为这里是稀疏图，所以我们用邻接表来存储。其他原理和朴素版的差不多。
这里详细讲函数内部的流程。

• 首先初始化dist数组和第一个节点和朴素版的一样
• 然后我们使用到了priority_queue结构，默认是大根堆，参数中加个greater<PII>就是小根堆，第一个参数填存储的数据类型，第二个参数把<>里面换成存储的数据类型就行了。
• 把第一个点加进去，注意第一个数是距离，第二个数才是节点的编号。
• 只要heap有数就执行，每次取出来堆顶，然后提取出来两个数。取出堆顶后就要把这个出堆。
• 这里要清除一下冗余数据，因为最小值可能之前用过了。
• 然后就是正常操作了。

源码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    // 这里的权重，是头节点，到该点的距离。
    // 如果有重边也没事，因为到时候堆中会选出最小的那个，然后其他的就continue了。
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 会优先对pair的第一个元素进行排序，如果第一个元素相等再对第二个元素进行排序。
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 第一个参数是数据类型，第二个参数是存储元素的底层容器，第三个代表小根堆。
    heap.push({0, 1}); // 第一个存的元素是距离， 第二个元素才是点的编号。

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        // ver 是点的编号，distance是边长。
        int ver = t.second, distance = t.first;

        /*
        这句是过滤掉冗余元素
        打个比方就是一个点到另一个点的距离有10，
        后来又加了15或者其他的更大距离，但是因为是小根堆，
        所以最短距离肯定会出现在最前面，所以除了在堆顶的元素，
        底下那些元素都算是冗余备份元素，可以舍弃掉了，直接continue就行。
        */
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    memset(h, -1, sizeof h);
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c);
    }

    cout << dijkstra() << "\n";

    return 0;
}