堆优化版Djikstra算法

首先是朴素算法原理

集合s ： 当前已经确定最短距离的点
① dis[1] = 0,dis[其他点] = 极大值。
② for( i从1到n）
{
    找到不在s中的 距离最近的点。（设为t） n^2次
    把t加入s        每个循环一次，总共n次
    用t更新其他点的距离（看一下从1->x点的距离是否大于1->t->x的距离，
如果大于则更新）               
         m 次
}

使用堆来查找最近点，优化之后为：

集合s ： 当前已经确定最短距离的点
① dis[1] = 0,dis[其他点] = 极大值。
② for( i从1到n）
{
    找到不在s中的 距离最近的点。（设为t） n次
    把t加入s        每个循环一次，总共n次
    用t更新其他点的距离（看一下从1->x点的距离是否大于1->t->x的距离，
如果大于则更新）                
        mlogn 次（堆中修改元素增加的时间复杂度）
}

堆有两种方式
手写堆        O(mlogn)
c++stl的优先队列        O(mlogm)
一般由于m<n^2 ,所以区别不大，但是优先队列可以使代码复杂，一般使用stl，
但是会稍微多存一些无用元素。

\\acwing 850
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef pair<int,int> PII;

const int N = 100010;
int n,m,idx=0;
int h[N],w[N],e[N],ne[N];    //w是权重
int dist[N];
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;//ver点的编号，distance点的距离
        if (st[ver]) continue;//如果ver点已经出队过了，跳过此点。
        
        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;
    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);
    }
    int t = dijkstra();

    printf("%d\n",t);
    
    return 0;
}