首页 文章 c++ spfa严格非简单次短路模板

c++ spfa严格非简单次短路模板

2022-05-28 14:47  浏览数:408  来源:小高高123    

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > g[5005];
int n,m;
int d[5005],d2[5005],cnt[5005];
bool inq[5005];
int INF=1e9;
bool fail;
void spfa(int start){
fill(d,d+n,INF);
fill(d2,d2+n,INF);
fill(inq,inq+n,false);
fill(cnt,cnt+n,INF);
fail=false;
d[start]=0;
cnt[start]=0;
inq[start]=true;
queue<int> q;
q.push(start);
while(!fail&&!q.empty()){
int dot=q.front();
q.pop();
inq[dot]=false;
for(int i=0;i<g[dot].size()&&!fail;i++){
int to=g[dot][i].first,weight=g[dot][i].second;
bool change=false;
if(d[dot]+weight==d[to]||d[dot]+weight==d2[to]);//如果有一样的话跳过
else if(d[dot]+weight<d[to]){
d2[to]=d[to];
d[to]=d[dot]+weight;
change=true;
}
else if(d[dot]+weight<d2[to]){
d2[to]=d[dot]+weight;
change=true;
}
if(d2[dot]+weight<d2[to]){
d2[to]=d2[dot]+weight;
change=true;
}
if(change){
if(!inq[to]){
inq[to]=true;
q.push(to);
}
}
}
}
}



声明:以上文章均为用户自行添加,仅供打字交流使用,不代表本站观点,本站不承担任何法律责任,特此声明!如果有侵犯到您的权利,请及时联系我们删除。

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)