admin管理员组文章数量:1624329
C++中使用优先队列需要包含头文件#include< queue >。
常用的方法:
1.push(type);
2.pop();
3.top();
4.empty();
声明格式为:
priority_queue<type,容器,优先级比较方式(为类或结构体)>:
/* 没看过STL实现priority_queue的源码,不确定这个格式准不准确 */
举例:
priority_queue<int,vector< int >,greater< int > > //小根堆
priority_queue<int,vector< int >,less< int > > //大根堆
对于基本类型,,也可以
priority_queue< int > //默认为vector,less< int >,即大根堆
对于自定义类型,需要自己定义比较函数或者重载运算符 ’ < ’
比如说:
struct node{
int a , b;
bool operator < (const node &x) const { //此处为优先级的比较
//大根堆
if(a == x.a)return b < x.b;
else return a < x.a;
}
//也可用友元
};
或者自定义 cmp:
class cmp{
public:
bool operator() ( node x, node y){ //y的优先级大
if(x.a == y.a)return x.b > y.b; //小根堆
else return x.a > y.a;
}
};
声明时 :
priority_queue< node >;
或者 priority_queue< node ,vector< node >, cmp>;
下面以dijkstra的堆优化来具体讲解priority_queue的应用:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 2510,inf = 0x3f3f3f3f,C = 6210;
typedef pair<int,int>pp;
class cmp{
public:
bool operator() (pp a,pp b){
return b.second <= a.second;
}
};
struct node{
int to,w,next;
}edge[2*C];
int head[N],v[N],d[N];
int cnt = 0;
int n,m;
void add(int a,int b,int c){
edge[cnt].to = b;
edge[cnt].w = c;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void dijkstra(int sv){
memset(d,0x3f,sizeof d);
d[sv] = 0;
int a = sv;
priority_queue< pp,vector<pp>,cmp > q;
q.push({a,d[a]});
while(!q.empty()){
auto h = q.top();
q.pop();
if(v[h.first])continue; /*某一个结点可能被不同点更新,
会多次入队,故需要排重。*/
v[h.first] = 1;
for(int i = head[h.first];~i;i = edge[i].next){
int b = edge[i].w,c = edge[i].to;
if(h.second + b < d[c]){
d[c] = h.second+b;
q.push({c,d[c]});
}
}
}
}
int main(){
int sv,ev;
cin>>n>>m>>sv>>ev;
for(int i = 0;i < N;i++){
head[i] = -1;
edge[i].next = -1;
}
for(int i = 0;i < m;i++){
int from,to,w;
cin>>from>>to>>w;
add(from,to,w);
add(to,from,w);
}
dijkstra(sv);
cout<<d[ev]<<endl;
return 0;
}
本文标签: 队列priorityqueueDijkstra
版权声明:本文标题:C++优先队列priority_queue的使用和应用(dijkstra堆优化) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728896300a1178453.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论