用dfs能做到时间复杂度O(n),因为每个点只会遍历一次

// Acwing852判断负环
#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
// #define int long long
typedef unsigned long long ull;
#define js                     \
  ios::sync_with_stdio(false); \
  cin.tie(nullptr)

const int N = 2005;
vector<pair<int, int>> e[N];
bool dp[N];
int n, d[N], stack[N], top = 1;//top必须从1开始
bool dfs(int a)
{
  bool res = 0;
  for (auto [b, w] : e[a])
    {
      if (!dp[b] && !stack[b])
        {
          dp[b] = 1;
          stack[b] = top;
          d[top] = d[top - 1] + w;
          // 其实真正的栈是d[]——存的是距离,stack[]记录的是相应的点在栈中的位置
          top++;
          res = max(dfs(b), res);
          top--;
          stack[b] = 0;
        }
      else if (stack[b])
        if (d[stack[b]] > d[top - 1] + w)
          return true;
    }
  return res;
}

void solve()
{
  //假设一个虚拟点s,有指向每个点的w==0的边，这样保证了是连通图，下面模拟从s开始遍历
  for (int i = 1; i <= n; i++)
    {
      if (!dp[i] && !stack[i])
        {
          dp[i] = 1;
          stack[i] = top++;
          if (dfs(i))
            {
              cout << "Yes";
              return;
            }
          top--;
          stack[i] = 0;
        }
    }
  cout << "No";
}

signed main()
{
  js;
  int m, a, b, w;
  cin >> n >> m;
  while (m--)
    {
      cin >> a >> b >> w;
      e[a].push_back({b, w});
    }
  solve();
  return 0;
}