社区讨论
卡常 求大佬指点
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 条回复,欢迎继续交流。
正在加载回复...