关于C++的priority_queue
  • 板块学术版
  • 楼主jia_hua_wu
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/11/16 21:16
  • 上次更新2023/10/27 02:44:04
查看原帖
关于C++的priority_queue
538899
jia_hua_wu楼主2022/11/16 21:16

最近在学Dijkstar算法的堆优化时,发现这么一个问题:对于STL库里的priority_queue容器,如果这样创建

priority_queue<pair<int,int> > q;

并且没有声明其他任何排序方式(就是只用默认的大根堆),它(程序)会以哪个值为标准排序?

放全代码(不是我的,是从一神犇那抄的)

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int N = 1e5+5;

int n,m,x,y,z;
int tot=0,s;
int d[N],v[N],hea[N];
priority_queue<pair<int,int> > q;
//大根堆(优先队列),第一维为d的相反数(变成小根堆),第二维为节点编号

struct Edge{
	int next,to,dis;
}edge[N<<1];//邻接表存储
void add(int x,int y,int z){
	edge[++tot].next=hea[x];
	edge[tot].to=y;
	edge[tot].dis=z;
	hea[x]=tot;
}//存下一条(x,y),权值为z的边(算法书上都有)

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}//邻接表存边
	
	for(int i=1;i<=n;i++){d[i]=inf;v[i]=0;}//重置
	
	d[s]=0;
	q.push(make_pair(0,s));//起点最短路为0,入队
	
	while(!q.empty()){//队列非空
		int x=q.top().second;q.pop();//取出堆顶
		if(v[x]) continue;
		v[x]=1;
		for(int i=hea[x];i;i=edge[i].next){//扫描所有出边
			int y=edge[i].to;
			if(d[y]>d[x]+edge[i].dis){
				d[y]=d[x]+edge[i].dis;
				q.push(make_pair(-d[y],y));
			}//松弛操作,插入堆
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",d[i]);
	return 0;
}
2022/11/16 21:16
加载中...