求助dijkstra懒惰删除
  • 板块学术版
  • 楼主Kirei
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/10/1 11:07
  • 上次更新2023/10/27 09:23:20
查看原帖
求助dijkstra懒惰删除
143050
Kirei楼主2022/10/1 11:07

我在费用流模板里使用了没有加势的dij,但它竟然直接通过了,后来发现是因为这句话

int x=q.top().se;
int dis=q.top().fi;
q.pop();
if(-dis!=d[x])continue;//即M_sea所言的懒惰删除

后来把它改成如下

int x=q.top().se;
int dis=q.top().fi;
q.pop();
if(vis[x])continue;
vis[x]=1;

就wa了,

有大佬能解释一下吗,

是数据水的缘故,还是它是对的,如果是正确的,复杂度又是多少?

2022/10/1 11:07
加载中...