社区讨论

为什么dij的优先队列用cmp会wa?

P4779【模板】单源最短路径(标准版)参与者 6已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi6wulfg
此快照首次捕获于
2025/11/20 12:07
4 个月前
此快照最后确认于
2025/11/20 12:07
4 个月前
查看原帖
CPP
struct node
{
    int u,d;
    bool operator<(const node& rhs)
    const
    {
        return d>rhs.d;
    }
};
void Dijkstra()
{
    priority_queue<node> q;
    for(int i=1;i<=n;++i) d[i]=2147483647;
    q.push((node){s,d[s]});
    d[s]=0;
    while(!q.empty())
    {
        node x=q.top();
        int u=x.u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                q.push((node){v,d[v]});
            }
        }
    }
}
nodeACnodeAC
CPP
struct cmp{
    bool operator()(int x,int y){
        return dis[x]>dis[y];
    }
};
priority_queue<int,vector<int>,cmp>q;
void dijkstra(){
    int u,v,w;
    dis[s]=0;q.push(s);
    while(!q.empty()){
        u=q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i;i=p[i].nxt){
            v=p[i].to;w=p[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push(v);
            }
        }					
    }	
}
cmpcmp 就只有 6060
某清华爷说是的距离的值改变的时候,节点编号在堆里的位置不变,但是 dijdij 不是每次改变距离的值的时候,同时 pushpush 节点编号吗

回复

7 条回复,欢迎继续交流。

正在加载回复...