P3385 【模板】负环 · znzryb
## 思路讲解
我实际上是用bellman-ford算法搞的。
那么如果松弛n次都没有松弛下来，就说明一定有负环，因为正常的最短路不会经过一个点多次。
## AC代码
[https://www.luogu.com.cn/record/210047386](https://www.luogu.com.cn/record/210047386)
其实也没有什么做不了的，如果dist[j]==INF，那么说明1点还没有到达过你这个点，那么就说明不能进行松弛操作，避免被hack
```cpp
1
4 3
2 3 -1
3 4 -1
4 2 -1
NO
```
```cpp
// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
inline void solve(){
cin>>N>>M;
vector<ll> dist(N+5,INF);
vector<vector<pll>> g(N+5);
FOR(i,1,M){
ll u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
if(w>=0){
g[v].pb({u,w});
}
}
dist[1]=0;
FOR(i,1,N+5){
bool flag=false;
FOR(j,1,N){
FOR(k,0,SZ(g[j])-1){
ll node=g[j][k].fi,w=g[j][k].se;
if(dist[node]>dist[j]+w && dist[j]!=INF){
dist[node]=dist[j]+w;
flag=true;
}
}
}
if(flag==false){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
https://www.luogu.com.cn/record/210043824
*/
```
## 心路历程（WA，TLE，MLE……）
这个下面的代码用来判断负环是没有问题的，问题在于bellman-ford算法无法判断是不是能从1到达这个负环。
[https://www.luogu.com.cn/record/210044531](https://www.luogu.com.cn/record/210044531)
```cpp
// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
inline void solve(){
cin>>N>>M;
vector<ll> dist(N+5,INF);
vector<vector<pll>> g(N+5);
FOR(i,1,M){
ll u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
if(w>=0){
g[v].pb({u,w});
}
}
dist[1]=0;
FOR(i,1,N+5){
bool flag=false;
FOR(j,1,N){
FOR(k,0,SZ(g[j])-1){
ll node=g[j][k].fi,w=g[j][k].se;
if(dist[node]>dist[j]+w){
dist[node]=dist[j]+w;
flag=true;
}
}
}
if(flag==false){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
https://www.luogu.com.cn/record/210043824
*/
```