其实堆优化版极其的简单，只要知道之前的Dijkstra怎么做，那么堆优化版就完全没有问题了。

在做之前，我们要先学会优先队列，来完成堆的任务，下面盘点了几种堆的表示方式。

priority_queue< pair<int,int> >q;// 这就是本程序要用的两个量的堆，当然这是大根堆，排的是第一个
q.qush(make_pair(0,1));//在程序中是这么用的，大根堆排序的是0
int x=q.top().second;//取第二个元素
int x=q.top().first;//取第一个元素
 
priority_queue<int>q; //这就是普通的大根堆
priority_queue<int,vector<int>,less<int> >q;//也可以这么写，但有前面一个很显然不会用这个

priority_queue<int,vector<int>,greater<int> >q;//这个是小根堆，一般性我们可以用大根堆来模拟小根堆，只要把元素变成负的就可以了。
q.push(make_pair(-dis[shu[w].to],shu[w].to));//在本程序中是这样用大根堆来起到小根堆的效果的，因为我没有找到怎么定义小根堆有两个量的方式

下面是优先队列的几种操作的方式：
int x=q.top();//取堆顶元素，除了一开始讲的两个量的堆，其它都是
q.pop();//删除堆顶元素
itn x=q.size();//堆的元素个数
q.push(int);//插入一个元素，它会自己排序的

以上就是本人对优先队列的了解。（真是个蒟蒻）

下面就是堆优化版的Dijkstra。还是借助代码来讲解。嗷嗷嗷，对了链式前向星还有一个更加大众的名字，邻接表。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int quan,qian,to;
 5 }shu[500010];
 6 int head[10010],ans,n,m,s,dis[10010];
 7 bool vis[10010];
 8 priority_queue< pair<int,int> >q; 
 9 void add(int x,int y,int z){
10     shu[++ans].qian=head[x];
11     shu[ans].quan=z;
12     shu[ans].to=y;
13     head[x]=ans;
14 }//邻接表，也就是链式前向星。
15 void Dijkstra(){
16     memset(dis,0x3f,sizeof(dis));
17     memset(vis,false,sizeof(vis));
18     q.push(make_pair(0,s));//存入编号，前面的0没有影响，因为一开始就被删掉，你可以想设什么设什么
19     dis[s]=0;
20     while (q.size()!=0){//如果堆中还有元素，也就是size不为0
21         int x=q.top().second;q.pop();//取编号，删掉堆顶
22         if (vis[x]) continue;//如果已经被找过那么就可以跳过了
23         vis[x]=true;//标记为已经找过
24         int w=head[x];//找到编号相对应的最后一条边
25         while (w!=0){//边界，把所有相关的边遍历一遍
26             if (shu[w].quan+dis[x]<dis[shu[w].to]){//更新距离
27                dis[shu[w].to]=shu[w].quan+dis[x];
28                q.push(make_pair(-dis[shu[w].to],shu[w].to));//用负数实现小根堆的操作，存入编号
29             }
30             w=shu[w].qian;//遍历前面一条边
31         }
32     }
33 }
34 int main(){
35     cin>>n>>m>>s;
36     ans=0;
37     for (int i=1;i<=m;i++){
38         int a,b,c;
39         cin>>a>>b>>c;
40         add(a,b,c);//存边
41     }
42     Dijkstra();
43     for (int i=1;i<=n;i++){
44           if (dis[i]>='100000') cout<<"2147483647 ";//如果数太大那么就没有路径可以相连
45         else cout<<dis[i]<<" ";
46     }
47 }

 

版权声明：本文为fnbk原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fnbk/p/9326212.html