优先队列怎么用

P4779 【模板】单源最短路径(标准版)

Soft_cute @ 2023-08-10 18:38:55

想要dijkstra+vector存边+堆优化代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e4+10,M=1e5+10;
int n,m,s,a[N][N];
struct Node{
    vector<int> childs;
    int dis;
    int deep;
    int size;
    bool f=false;
}g[N];
struct cmp{
    bool operator() (const Node &a,const Node &b){
        return a.dis>b.dis;
    }
};
void add(int x,int y,int z){
    g[x].childs.push_back(y);
    g[y].childs.push_back(x);
    g[x].size=x,g[y].size=y;
    a[x][y]=a[y][x]=z;
}
void dijkstra(){
    for(int i=1;i<=n;i++) g[i].dis=inf;
    priority_queue<Node,vector<Node>,cmp> heap;
    heap.push(g[1]);
    while(heap.size()){
        Node t=heap.top;
        heap.pop();
        int ver=t.size,distance=t.dis;
        if(g[ver].f) continue;
        g[ver].f=true;
        for(int i=0;i<g[ver].childs.size();i++){
            int j=g[ver].childs[i];
            if(g[j].dis>distance+a[i][j]){
                g[j].dis=distance+a[i][j];
                heap.push(g[j]);
            }
        }
    }
    if(g[n].dis==inf) return -1;
    return g[n].dis;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        add(x,y,c);
    }
    cout<<dijkstra();
} 

我写的不怎么对,不知道优先队列怎么用


by mmr123 @ 2023-08-10 18:42:06

<类型,实现,比较器>


by KAqwq @ 2023-08-10 18:44:37

priority_queue<Node,vector<Node>,greater<Node> >

之后看看有没有别的问题


by Soft_cute @ 2023-08-10 18:46:00

实现是什么?


by pengrongxuan @ 2023-08-21 20:49:42

优先队列公式:

priority_queue<类型> 队列名称;

如:

priority_queue<int> q;

如果有多个数据,需要:

priority_queue<pair<类型1,类型2> > 队列名称;

如:

priority_queue<pair<int,int> > q;//最后的两个右括号需要分开一个空格,不然会被认为是右移>>运算符

优先队列函数:

q.size();//返回q里元素个数
q.empty();//返回q是否为空,空则返回1,否则返回0
q.push(k);//在q的末尾插入k,多个数据需要使用
//q.push(make_pair(a,b));
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.top().first;//返回q的第一个元素的第一项
q.top().second;//返回q的第一个元素的第二项

|