C++ 代码

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

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];

//有重边也不要紧，用邻接表存储时，算法保证了会选择距离最小的点
// 假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
// 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径）
// ，并标记st为true，所以下一次弹出3+x会continue不会向下执行。
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中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，其次在从堆中拿出来的时    
    // 候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。

    heap.push({0, 1});//first表示距离，second表示点的编号
    // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序

    // 遍历所有的边,至多m次
    while(heap.size())
    {
        auto t=heap.top();//O(m) * O(1) -> O(m)
        heap.pop();

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

        if(st[ver]) continue;//处理冗余的点，就是已经确定了最短距离的点，直接跳过
        st[ver]= true;//O(m) * O(1) -> O(m)

        for(int i=h[ver]; i!=-1; i=ne[i])
        {
            int j=e[i];
            if(dist[j]> dist[ver]+w[i]) //for循环加这个if会遍历邻接表所有的边，执行m次没有重复，只有当if为真时，才会push。所以heap.push最多执行m次
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j], j});
                // 堆的插入操作时间复杂度是 O(log(n))
                 // O(m) * O(log(n)) -> O(mlog(n))
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    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);
    }

    cout<< dijkstra()<<endl;

    return 0;
}