题目链接

洛谷P4779 Dijkstra优先队列优化 模板

参考博客

这个大佬把好多单源最短路径问题的解法代码都写了一遍，tql！！！
大佬

优先队列优化Dijkstra算法

学了一晚上终于看明白了，因为大佬觉得很简单，所以注释并不细致，导致我这个小白理解了好久。
首先说明，要是不知道Dijkstra算法，先看看“啊哈C”里对于此算法的讲解再看此优化题解。
进入正题：
优先队列，通过堆实现，即二叉树，只要知道它是个队列，队首总是放着最大或者最小的数（默认是最大的数，可以手动调整为最小数在队首）。
优化正是利用了优先队列的这个特性。
还是通过代码注释来讲解。
先提醒一下，代码中嵌套使用了许多STL容器，所以理解起来比较困难，但不要放弃，多读几遍，一定会懂！我就是这样的！更何况我会详细的讲解，你还有什么理由放弃！

AC代码（模板）

#include<bits/stdc++.h>
#define pb push_back//！！！
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int n,m,s;
struct edge{
    int to,cost;
};//to代表点的编号，cost代表某个点到to点的权值。配合下面的vector G理解一下。
typedef pair<int,int> P;//下面所用到的P，P.second代表一个点的编号，P.first表示起点s到P.second的距离。（下面会讲为什么first代表距离，second代表编号）
//对了，还得补充一下，pair可以比较大小，他们比较大小的方式是先比较first，若同，再比second。
vector<edge> G[N];
/*
G[v][i].to表示与v点相连的第i个点的编号，G[v][i].cost表示v点与v点相连的第i个点之间的距离，这个距离仅仅是输入时候的那个距离，在整个程序运行的过程中是不变的，也就是说我们只是用这里面存储的值，却不更新存储的值。
*/
int d[N];//存储起点到其他各点的距离
void create(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int from,to,cost;
        cin>>from>>to>>cost;
        edge tmp;
        tmp.to=to;tmp.cost=cost;//把tmp结构体赋值好，放在G容器中
        G[from].pb(tmp);//之所以struct edge中不定义from变量，正是因为G的索引已经表明了tmp.to的起点（此起点为某条边的起点，并非起点s），没必要再定义from变量存起点了。
    }
    fill(d+1,d+n+1,INF);
    /*
    find函数，在c++中用于全部赋值，有点类似于memset，但是显然比memset好用。
    前俩参数和sort中的前俩参数一个意义，第三个参数是被赋予的值。
    这里，我们先让全部点之间的距离都赋值为INF，保证通过比较大小更新距离
    */
}//这样看来，这整个过程无非就是输入数据并创建了个G，用来存储边与边权，同时对d数组进行了初始化。其实，G才是重点。
void Dijkstra(){
    priority_queue<P, vector<P>, greater<P> > que;
    /*
    懵了没？我当时懵了。
    尖括号内三个东西，其中，第一个P表示que中存储的类型；第二个vector<int>填写的是来承载底层数据结构堆(heap)的容器，第三个若为less<int>表示数字大的优先级越大，若为greater<int>表示数字小优先级越大。
    按照greater存放，实现了把小的数存在队首，可以通过top直接取出最小的数，不用再像老版中Dijkstra中循环找最小值更新了，我们直接取出已经排号的最小数就行了，方便的很！
    注意，vector，greater里的类型都是pair类型！
    */
    que.push(P(0,s));
    /*
    P(0,s)等价于pair<int,int> p(0,s)，就是把一个pair初始化了，只不过P(0,s)这样初始化并没有明确地把这俩数赋到某个pair类型的变量上，而是直接入栈了。
    语句含义：把s点和s点到s点的距离0，打包入栈。（如果这里忘记了P的含义，往上面翻翻再看看）
    */
    d[s]=0;//起点s到起点s的距离设置为0；
    while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(d[v]!=p.first) continue;//就是这个语句，大佬的注释都极其模糊，甚至不注释，我想了好久这里，想明白这里之后直接豁然开朗，整个代码都明了了。
                /*下面的几句话实现的是刷新某点到起点s的最短距离，但是刷新前的点的信息依旧在队列里，我们得把它们弹出，判断哪些是失效的信息的标准就是比较 通过已刷新的数组d去访问此点到起点s的距离 与 通过队列里的first去访问此点到s点的距离，相等说明没刷新，不相等说明刷新了，你已经没用了，可以弹出了，因为我们已经保存了最新信息。
                再说简单点，刷新之后的某点对应的d值应该是要等于p.first的，不等于的话，说明d更新了，p.first没更新，信息失效，弹出。
                 */   
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];//暂存一下v连着点的信息
            if(d[e.to]>d[v]+e.cost){//e.to是与v相连点的编号，e.cost是二者的边权
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));//这才是刷新之后的有效信息，压入了，所以上面代码就可以把之前压入栈中的信息弹出了。
            }
        }
    }
}
void output(){
    for(int i=1;i<n;i++) cout<<d[i]<<' ';
    cout<<d[n];//最后一个不输出空格而已
}//简单至极，输出而已
void solve(){
    create();//创建过程
    Dijkstra();//核心代码
    output();//输出
}
int main(){
    solve();
}