负环spfa
wenge
2020-02-12 22:06:15
```cpp
ll n,m,s,t;
vector<ll> f[N],g[N];
ll vis[N],dis[N];
int spfa(ll s){
for(int i=1;i<=n;i++)dis[i]=inf;
queue<ll> q;
q.push(s);
dis[s]=0;
while(!q.empty()){
ll x=q.front();
q.pop();
if(vis[x]>n){
return 1;//loop
}
vis[x]++;
for(int i=0;i<f[x].size();i++){
ll y=f[x][i];
if(dis[x]+g[x][i]<dis[y]){
dis[y]=dis[x]+g[x][i];
q.push(y);
}
}
}
return 0;
}
```