Dijkstra求最短路 II（堆优化Dijkstra算法）

给定一个?n?个点?m?条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出?11?号点到?n?号点的最短距离，如果无法从?11?号点走到?n?号点，则输出??1?1。

输入格式

第一行包含整数?n?和?m。

接下来?m?行每行包含三个整数?x,y,z，表示存在一条从点?x?到点?y?的有向边，边长为?z。

输出格式

输出一个整数，表示?1?号点到?n?号点的最短距离。

如果路径不存在，则输出??1?1。

数据范围

1≤n,m≤1.5×10^5，
图中涉及边长均不小于?0，且不超过?10000。
数据保证：如果最短路存在，则最短路的长度不超过?10^9。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

思路：这道题的堆优化我们使用优先队列来做（小根堆），而且因为我们既要存当前点到起点的距离，又要存当前点的编号，所以我们使用一个pair，又因为我们是根据距离来判断入堆的时机的（每次离起点最近的点入堆），所以优先排序的是距离，也就是pair的first元素应该是距离。

    typedef pair<int,int> PII;

    priority_queue<PII,vector<PII>,greater<PII>> heap; // 数据类型， 容器， 排序方式
    //定义一个升序的优先队列（小根堆）
    
    heap.push({0,1});  //放入距离，节点编号，这里1号点到1号点的距离是0 
   //这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    

先看完整代码?

示例代码：

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

using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int n,m;
int h[N],e[N],ne[N],w[N],idx; //稀疏图用邻接表存，w存边权值
int dist[N];  //1号点到n号点的最短距离
int st[N];  //当前点是否找到了最短距离

void add(int a,int b,int c) //添加一条从a指向b的边
{
    e[idx]=b;  //算法保证了会选出最短的路，所以不对重边或自环情况做处理，也就是会存在冗余
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}

int dijkstra() //输出一个整数，表示1号点到n号点的最短距离。
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    
    priority_queue<PII,vector<PII>,greater<PII>> heap; // 数据类型， 容器， 排序方式
    //定义一个升序的优先队列（小根堆）
    
    heap.push({0,1});  //放入距离，节点编号，这里1号点到1号点的距离是0 
   //这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    
    while(heap.size())
    {
        auto t=heap.top(); //每次找到堆里面最小距离的点，也就是不在集合S中距离最短的点
        heap.pop();
        
        int ver=t.second,distance=t.first; //ver是节点编号，distance是点的距离
        
        if(st[ver]) continue; //如果ver这个点之前出来过，说明当前这个点是冗余（重边自环之类的），也就没有必要继续处理，直接continue，不再执行下面的语句，而是执行下一次的while循环
        
        /*
        堆优化版的是将距离直接加入到堆中.
        例如:dist[5]=9(在堆中{9,5},第一次更新时加入),dist[5]=7(在堆中{7，5},第二次更新时加入)
        使用时用的是dist[5]=7,将该点({7,5})弹出后,在下一次循环中,如果{9,5}在堆顶的话,使用时
        两者间肯定要选距离要小的那个,不能使用{9,5}重复更新,所以要用st数组进行标记
        */
        
        st[ver]=true; //如果这个点之前没有出来过，就标记找到了这个点的最短距离
        
        for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点，i是当前点ver指向的点的下标（与当前点与连线的点）
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号（i存的是下标，下标对应的点的值就是结点编号）
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离，再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)
    {
        return -1;
    }
    return dist[n];
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

//一个点到另一个点的距离有10，后来又加了15或者其他的更大距离，但是因为是小根堆，所以最短距离肯定会出现在最前面
//所以除了在堆顶的元素，底下那些元素都算是冗余备份元素，可以舍弃掉了，直接continue就行。

代码基本都比较好理解，注意这道题用邻接表存，其中e[ ]存的就是节点编号

 for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点，i是当前点ver指向的点的下标（与当前点与连线的点）
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号（i存的是下标，下标对应的点的值就是结点编号）
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离，再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }

关于w[i]和i，j在这里面都代表什么：

 while(heap.size())
    {
        auto t=heap.top(); //每次找到堆里面最小距离的点，也就是不在集合S中距离最短的点
        heap.pop();
        
        int ver=t.second,distance=t.first; //ver是节点编号，distance是点的距离
        
        if(st[ver]) continue; //如果ver这个点之前出来过，说明当前这个点是冗余（重边自环之类的），也就没有必要继续处理，直接continue，不再执行下面的语句，而是执行下一次的while循环
        
        /*
        堆优化版的是将距离直接加入到堆中.
        例如:dist[5]=9(在堆中{9,5},第一次更新时加入),dist[5]=7(在堆中{7，5},第二次更新时加入)
        使用时用的是dist[5]=7,将该点({7,5})弹出后,在下一次循环中,如果{9,5}在堆顶的话,使用时
        两者间肯定要选距离要小的那个,不能使用{9,5}重复更新,所以要用st数组进行标记
        */
        
        st[ver]=true; //如果这个点之前没有出来过，就标记找到了这个点的最短距离
        
        for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点，i是当前点ver指向的点的下标（与当前点与连线的点）
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号（i存的是下标，下标对应的点的值就是结点编号）
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离，再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }
    }

为什么要有continue和冗余？

代码中的for循环会把所有满足dist[j] > distance + w[i]的点都加进去，有的点它既是a的邻接点又是b的邻接点，这样的点可能会在将a的邻接点更新的时候加进去一次，又在更新b的邻接点的时候又加进去一次，这样队列中就有两个一样的点，虽然距离不同，此时这两个一样的点拓展的点也是一样的，所以我们取距离短的就好。

最后：

连线很多的时候，对应的就是稠密图，显然易见，稠密图的路径太多了，所以就用点来找，也就是抓重点；
点很多，但是连线不是很多的时候，对应的就是稀疏图，稀疏图的路径不多，所以按照连接路径找最短路，这个过程运用优先队列，能确保每一次查找保留到更新到队列里的都是最小的，同时还解决了两个点多条路选择最短路的问题；

参考：AcWing 850. Dijkstra求最短路 II - AcWing