分析

上一次我已经对 朴素版的Dijkstra算法做了一个大致的说明；朴素版Dijkstra算法的时间复杂度是$O(n^2)$的,适用于稠密图，即点少边多的情况，假如点数变的很大了比如10^5了，那么显然朴素版就会爆掉了。此时对于稀疏图(点和边差不多一样)就要使用堆优化的Dijkstra算法了，其本质只不过是对朴素版本找最小值的操作做了一个优化，即使用了数据结构堆，把找最小值的操作优化到O(1)，而把更新点的时间变到了$O(mlogn)$，在下面的代码中对堆优化的Dijkstra算法的时间复杂度做了一个详尽的说明。

然后还有一点需要注意的是，对于稠密图我们用邻接矩阵存储，此时由于点到点之间在邻接矩阵中只能存一条边，因此每次我们挑选最短距离的一条边存放进去。
但是对于稀疏图我们选择采用了邻接表的形式进行存储，此时就无需对这些重边什么的进行处理了，直接add进去就好了。

代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define fi first
#define se second

const int N=1e5+10;
int h[N],w[N],e[N],ne[N],idx=0;//稀疏图使用邻接表来进行存储
int dist[N];//各点到源点的距离
bool st[N];//该点是否已加入集合
typedef pair<int,int> PII;//到源点距离，点的下标

int n,m;

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

int dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push({0,1});
    while(q.size()){
        //拿到当前距离源点距离最短的点——O(1)
        PII p=q.top();
        q.pop();
        int pos=p.se,dis=p.fi;
        if(st[pos]) continue;
        st[pos]=true;
        //用该点去更新其他与之相连的点，相当于是在遍历边;从全局来看总共会遍历m条边，假如每次都更新了点的话，更新
        //一次的时间复杂度是O(logn) 因此总的时间复杂度就是O(mlogn)
        for(int i=h[pos];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dis+w[i]){
                dist[j]=dis+w[i];
                q.push({dist[j],j});
            }
        }
    }

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

    return  0;
}