书接上回 https://www.acwing.com/file_system/file/content/whole/index/content/1130528/#comment_37626

算法 堆优化Dijkstra

朴素版Dijkstra总结有6步

1.把所有点到起点的距离都初始化为正无穷，起点到自己的最短距离为；

2.进行n次操作确定n个点的最短距离（把所有点都加入到st集合中）；

3.每次从集合中选出不在集合中且到起点最短的那个点；

4.把此点加入到集合st中；

5.再以此点为中心向其连接的点进行扩展，并插入到堆里

6.最后返回终点到起点的最短距离就行了

<1>分析朴素算法慢在那一步上（按步骤的时间复杂度分析）

第1步O(1)
第2步O(n)外层循环
第3步O(n*n)
第4步O(n)
第5步O(m)他最多遍历m条边
第6步O(1)

综上所述最慢就事慢在第3步上，所以考虑怎样进行对第3步的优化

<2>怎样优化慢的那一步

因为是取最小值所以可以考虑有堆这个数据结构来优化其步骤

堆可以用 log n 的时间帮我们找到最小的那个数

所以第3步就可以优化到n log n;

但是有一个问题

就是在第5步的时候：插入数据的时候就不是直接O(1)就进去了，而是因为得条整堆内元素，所以由原来的O(1)时间插入数据变成了O(log m)；

所以这一步的总时间就是O(m log m);

又因为这是最慢的，所以整个算法的时间复杂度就差不多是O(m log m);

<3>怎样选择
现在有两个一个是手写堆，一个是STL的优先队列
手写堆：好处：时间复杂度O(m log n);空间耗用少；
坏处：太麻烦，代码极其长，思路极其奇葩(还得存映射)
STL的优先队列：好处：代码短，好理解
坏处：时间复杂度是O(m log m);

此题是一个稀疏图，m和n是一个数量级的，为了考试，为了偷懒，STL万岁！！！

所以O(m log n),和O(m log m)是差不多的;

时间复杂度 O(m log n);

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int e[N],h[N],w[N],ne[N],idx,dist[N],st[N],n,m;
typedef pair<int,int>PII;
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 v=t.second;
        if(st[v])continue;

        st[v]=1;
        for(int i=h[v];~i;i=ne[i])
        {
            int u=e[i];
            if(dist[u]>dist[v]+w[i])
            {
                dist[u]=dist[v]+w[i];
                heap.push({dist[u],u});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
}

如有不严谨之处请谅解，大佬勿喷！！！