AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 852. spfa判断负环

作者: 作者的头像   Yangchang ,  2023-01-25 22:24:11 ,  所有人可见 ,  阅读 8


0


#include<bits/stdc++.h>
#define inf (int)((1u<<31)-1)
using namespace std;
using cint = const int&;
using pii = pair<int,int>;
const int maxm = 5e5+10,maxn = 1e5+10;
//Tip1: Basic 
struct {
    int nxt,v,w;
}edge[maxm];
int head[maxn],ecnt,n,m,s,a,b,c,qcnt[maxn];
bool vis[maxn];
inline void addedge(cint u,cint v,cint w){
    edge[++ecnt] = {head[u],v,w};
    head[u] = ecnt;
}
//Tip2: MinDis
/// Tip2.1 Dijkstra && SPFA
int dis[maxn];
inline void dijkstra(cint s,cint n){
    memset(vis+1,0,n);
    //memset(dis+1,inf,n * sizeof(dis[0]));
    fill(dis+1,dis+n+1,inf);
    static priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({dis[s] = 0,s});
    while(!pq.empty()){
        const pii tp = pq.top();pq.pop();
        const int u = tp.second, du = tp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w) pq.push({dis[v] = du + w, v}); 
        }
    }
}
inline bool spfa(cint s,cint n){
    memset(vis+1,0,n);
    fill(dis+1,dis+n+1,inf);
    dis[s] = 0;
    static deque<int> q;
    q.push_back(s);

    while(!q.empty()){
        const int u = q.front(),du = dis[u];q.pop_front();
        vis[u] = 0;
        if(++qcnt[u] == n+1) return 1;
        for(int i = head[u];i;i=edge[i].nxt){
            const auto v = edge[i].v,w = edge[i].w;
            if(dis[v] > du + w){
                dis[v] = du + w; 
                if(!vis[v]){ if(1 || dis[v] < dis[q.front()]) q.push_back(v);else q.push_front(v);vis[v]=1;}
            }
        }
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=m;++i){
        cin>>a>>b>>c;
        addedge(a,b,c);

    }
    for(int i = 1;i<=n;++i) addedge(0,i,0);
    if(spfa(0,n)) cout<<"Yes";
    else cout<<"No";
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息