AcWing 850. Dijkstra求最短路 II

解题思路

使用堆优化后的Dijkstra算法，时间复杂度为 $ O(m log n) $，$ m $ 表示边数，$ n $ 表示点数

依旧是惯例写一个邻接表，这里多定义一个w[]数组，来表示每条边的权值

然后就是每次从没确定且距离最近的点中挑出来一个，进行搜索，然后标记已搜索

代码中有两处用到了memset

第一处是memset(dist, 0x3f, sizeof dist);，这是对距离的赋值，方便一会进行更小值更新

另一处是memset(h, -1, sizeof h);，一直写邻接表的同学应该知道，这是对于邻接表头节点的初始赋值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;
typedef pair<int, int> PII; // first存储当前总距离，second存储点的序号

const int N = 1e6 + 10;

int dist[N];    // 已经确定的到每个点的距离进行存储
int n, m;   // n -> 点数，m -> 边数
int h[N], e[N], w[N], ne[N], idx;   // 邻接表所需数组
bool st[N];

// 邻接表插入边的操作
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;    // 小根堆，每次取出当前最近的点
    heap.push({0, 1});

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

        int ver = t.second, distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

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

    if(dist[n] == 0x3f3f3f3f) return -1;    // dist[n]仍然是INF，说明从1出发无法到达n
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while(m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dijkstra());

    return 0;
}