转自 https://blog.csdn.net/qq_41754350/article/details/83210517
再求单源最短路径时，算法有优劣之分，个人认为在时间方面 朴素dijkstra>bellmanford>SPFA>dijkstra+heap，所以掌握dijkstra堆优化对于OIER是必要的。
本文主要解说迪杰斯特拉堆优化的板子以及它所用到的知识；dijkstra算法、快读、stl以及链式前向星请自行百度或者看我的其他文章。
代码如下，注释个人觉得已经很清楚了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int cnt=0;//边的序号
int dis[5000010],vis[5000010],h[5000010];//dis：起点到该点的长度 vis：是否访问过了 h：起点为h[?]的暂存平台
struct node//next：下一个连接某个点的下一条边 to:该边指向的下一条边 val：边权
{
int next,to,val;
//int from; from在链式前向星的遍历里意义不大
}edg[5000010];
struct heapnode//重载小根堆
{
int num,dist;//num：标号 dist:距离
bool operator<(heapnode t) const//记住这种特殊写法就可以了
{
return dist>t.dist;//与sort相反，此处为从小到大
}
};
priority_queue<heapnode>q;//定义一个heapnode形式的优先队列q
int cread()//快读
{
int f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void add(int u,int v,int val)
{
++cnt;//一条新边
edg[cnt].to=v;//记录到哪里
edg[cnt].val=val;//记录边权
edg[cnt].next=h[u];//链式前向星的菊花搜图法
h[u]=cnt;//暂存桌面
}
int main()
{
int n,m,s;//n：点数 m：边数 s：起点
n=cread();m=cread();s=cread();
int x,y,z;
for(int i=1;i<=m;i++)
{
x=cread();y=cread();z=cread();
add(x,y,z);
}
for(int i=1;i<=n;i++)dis[i]=0x7fffffff;//初始化极大值需要用for，memset会出错
memset(vis,0,sizeof(vis));//初始化访问标记
dis[s]=0;//起点到起点自然为0
heapnode tem;//定义一个跑腿tem
tem.dist=0;tem.num=s;//记录起点信息
q.push(tem);//跑腿记录的东西入队
while(!q.empty())//队不空
{
heapnode u=q.top();//使用u记录队首信息（最小值）
q.pop();//队首gg
if(vis[u.num])continue;//假如已经访问过了，跳过
vis[u.num]=1;//标记访问过了
for(int i=h[u.num];i!=0;i=edg[i].next)//链式前向星式菊花搜图
{
int v=edg[i].to;//记录某条边的到达处
if(!vis[v]&&(dis[v]>dis[u.num]+edg[i].val))//假如说v没被访问过并且原来到v的路程大于从这条边经过的到v路程
{
dis[v]=dis[u.num]+edg[i].val;//更新到v的路程
tem.num=v;tem.dist=dis[v];//跑腿记录v的信息
q.push(tem);//跑腿入队
}
}
}
for(int i=1;i<=n;i++) printf("%d ",dis[i]);//到每个点的距离输出
return 0;
}