思路：

（1）負環：區別于正環，在求最短路過程中，正環會繞路，故不會被討論，而負環會不斷讓路總權更短，會讓算法不斷循環；

（2）于是考慮統計spfa最短路算法走過的路徑數，如果路徑數超過合理值n - 1,說明必然存在負環；

（3）于是對spfa算法做適當修改，

1. 一方面為防止1到不了負環，于是率先將所有點都提前放進隊列中；
2. 另一方面在更新距離時統計該路徑邊數;
3. 由于只要存在負環，就會不斷循環，所以無需將dist[]初始化。

代碼：

#include<bits/stdc++.h>using namespace std;const int N = 150000;int n,m;
int h[N],st[N],e[N],ne[N],idx,dist[N],w[N],cnt[N];void add(int a,int b,int c)
{e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}bool spfa()
{queue<int> q;for(int i = 1;i <= n;i ++)  {q.push(i);st[i] = 1;}while(!q.empty()){auto t = q.front();q.pop();st[t] = 0;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j]  = dist[t] + w[i];cnt[j] = cnt[t] + 1;if(cnt[j] >= n) return true;if(!st[j]){q.push(j);st[j] = 1;}}}}return false;}int main()
{memset(h,-1,sizeof h);cin >> n >> m;while(m --){int a,b,c;cin >> a >> b >> c;add(a,b,c);}if(spfa()) printf("Yes");else puts("No");return 0;
}