我在费用流模板里使用了没有加势的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了,
有大佬能解释一下吗,
是数据水的缘故,还是它是对的,如果是正确的,复杂度又是多少?