社区讨论
为什么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]});
}
}
}
}
用 了
CPPstruct 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);
}
}
}
}
用 就只有
某清华爷说是的距离的值改变的时候,节点编号在堆里的位置不变,但是 不是每次改变距离的值的时候,同时 节点编号吗
回复
共 7 条回复,欢迎继续交流。
正在加载回复...