最近在学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;
}