社区讨论

卡常 求大佬指点

P3385【模板】负环参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6te9wl
此快照首次捕获于
2025/11/20 10:31
4 个月前
此快照最后确认于
2025/11/20 10:31
4 个月前
查看原帖
GG
代码如下:
CPP
#include <iostream>
#include <cstring>
using namespace std;
int head[330000],a[410000],aw[410000],al[410000];
bool visit[330000];
const int maxn=2147483647;
int dis[330000];
int n,m,an=0;
bool flag=0;
void addline(int u,int v,int w){
    an++;
    a[an]=v;aw[an]=w;al[an]=head[u];
    head[u]=an;
    return;
}
inline void dfs_spfa(int p){
    if(flag)return;
    visit[p]=1;
    for(int l=head[p];l!=0;l=al[l])  
        if(dis[a[l]]>dis[p]+aw[l]){
            if(flag)return;
            dis[a[l]]=dis[p]+aw[l];
            if(visit[a[l]]){
                flag=1;
                return;
            }
            dfs_spfa(a[l]);
        }
    visit[p]=0;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    int T;
    cin>>T;
    int i;
    int u,v,w;
    while(T>0){
        T--;
        cin>>n>>m;
        memset(al,0,sizeof(al));
        memset(head,0,sizeof(head));
        memset(visit,0,sizeof(visit));
        an=0;
        flag=0;
        for(i=1;i<=m;i++){
            cin>>u>>v>>w;
            addline(u,v,w);
            if(w>0)addline(v,u,w);
        }
        for(i=1;i<=n;i++){
            for(int i1=1;i1<=n;i1++)dis[i]=maxn; 
            dis[i]=0;
            dfs_spfa(i);
            if(flag)break;
        }
        if(flag)cout<<"YE5"<<endl;
        else cout<<"N0"<<endl;
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...