bool bf() {
memset(dis,INF,sizeof(dis));
dis[1]=0;
for(int j=1; j<=n-1; j++) {
for(int i=1; i<=m; i++) {
dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);
if(w[i]>=0)
dis[u[i]]=min(dis[u[i]],dis[v[i]]+w[i]);//双向边
}
}
//多一次松弛
for(int i=1; i<=m; i++) {
if(dis[u[i]]!=INF&&dis[v[i]]>dis[u[i]]+w[i])return 1;
if(w[i]>=0) {
if(dis[v[i]]!=0x7f&&dis[u[i]]>dis[v[i]]+w[i])return 1;//双向边
}
}
return 0;
}
2020.8.26 UPDATE
vector<pair<int,int> >G[50003];
struct SPFA_WITH_NEG_CIRC {
const static int MAXN = 50000;
int dis[MAXN+5],dpt[MAXN+5];
bool vis[MAXN+5];
bool spfa(int S,bool cir=0) {
for(int i=0; i<=n; i++)dis[i]=0x7ffffff,vis[i]=dpt[i]=0;
dis[S]=0;
deque<int>q;
q.push_back(S);
while(!q.empty()) {
int x=q.front();
q.pop_front();
vis[x]=0;
int sz=G[x].size();
for(int i=0; i<sz; i++) {
int y=G[x][i].first,w=G[x][i].second;
if(dis[y]>dis[x]+w) {
dis[y]=dis[x]+w;
if(!vis[y]) {
vis[y]=1;
if(cir&&++dpt[y]>=n)return 1;
if(cir)q.push_back(y);
}
}
}
}
return 0;
}
} T;
No responses yet