Dijkstra堆优化版

适用于稀疏图。

可以用堆优化Dijkstra算法，原因如下：
①堆可以动态维护一个集合中的最小值。
②堆动态支持插入、删除、改变一个数。
时间复杂度：O(m log n)

• 下面给出的代码中，我们使用的是手写堆。虽然也可以用STL中的 priority_queue，但是手写堆速度更快。
• P.S.存储图时用邻接表存储

//Dijkstra堆优化版 
#include<bits/stdc++.h>
#define N 1000+10
#define M 4000+10 
using namespace std;

int n/*点数*/,m /*边数*/;
int h[N],e[M],ne[M],v[M]/*权重*/,idx;//邻接表，存储边 
int hv[N]/*堆里面的值*/,ph[N]/*第i个点在堆里面的下标*/,hp[N]/*堆里面的某个下标对应的点*/,size/*堆的大小*/;//建立一个手写堆 
int dist[N];//存储每条边到原点的距离

void add(int a,int b,int c){//加边操作 (把a->b,长度为c的边添加到邻接表里)
    e[idx]=b;v[idx]=c;ne[idx]=h[a];h[a]=idx++;
} 

//堆操作
void heap_swap(int a,int b){//交换操作 
    //映射交换 
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);

    //堆值交换 
    swap(hv[a],hv[b]); 

} 
void down(int u){//下移操作 
    int t=u;//存贮最小值 
    if(u*2<=size&&hv[u*2]<hv[t])//如果当前点有左儿子并且左儿子的值比最小的点要小 
        t=u*2;
    if(u*2+1<=size&&hv[u*2+1]<hv[t])//如果当前点有右儿子并且右儿子的值比最小的点要小 
        t=u*2+1;
    if(t!=u){//如果u不是最小值 
        heap_swap(t,u);//把两个点交换 
        down(t);
    } 
}

void up(int u){//上移操作 
    while(u/2&&hv[u/2]>hv[u]){//如果当前点有父节点并且父节点值比当前结点值大 
        heap_swap(u/2,u);//与父结点交换 
        u/=2;
    }
}

void dijkstra(){
    //初始化 
    memset(dist,0x3f,sizeof(dist));
    memset(hv,0x3f,sizeof(hv));
    for(int i=1;i<=n;i++)ph[i]=hp[i]=i;
    dist[1]=hv[1]=0;size=n;

    for(int i=0;i<n-1;i++){
        //找出剩下点中距离原点最小的点 
        int t=hp[1];//t取堆顶结点编号 
        heap_swap(1,size--);down(1);//把t号点从堆中删除（堆尾移到堆顶，下移堆顶） 

        //从1号点到j号点的距离能否用经过t的一条路径来更新
        //即1->j能否用1->t和t->j路径来更新 
        for(int p=h[t];~p;p=ne[p]){//枚举t的出边 
            int j=e[p];//用j来表示出边的编号 

            if(dist[j]>dist[t]+v[p]){//如果需要更新 
                //更新 
                dist[j]=dist[t]+v[p];
                hv[ph[j]]=dist[j];//更新堆里的值 
                down(ph[j]);up(ph[j]);//维护堆 
            }

        }
    }
}

int main(){
    cin>>m>>n;

    memset(h,-1,sizeof(h));//将链表头初始化成-1 

    while(m--){//存储每条边 
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);add(b,a,c);
    } 

    dijkstra();
    cout<<dist[n];//输出1号点到n号点的最短距离 

    return 0; 
}