spfa求负环
/*
不用初始化 dist 0x3f的距离的原因 因为要找负环 所以正的地方不用放进去
只要经过边数大于=n 就是有负环
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n,m;
const int N = 2010;
typedef pair<int, int> PII;
typedef long long LL;
LL dist[N];
bool st[N];
vector<PII> u[N];
int cnt[N];
void spfa()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
q.push(i);
st[i]=1;
}
int flag=0;
while(q.size()&&!flag)
{
int t=q.front();
q.pop();
st[t]=0;
int len=u[t].size();
for(int i=0;i<len;i++)
{
int id=u[t][i].first;
int dd=u[t][i].second;
if(dist[id]>dist[t]+dd)
{
if(!st[id])
{
q.push(id);
st[id]=1;
}
cnt[id]=cnt[t]+1;
if(cnt[id]>=n)
{
flag=1;
break;
}
dist[id]=dist[t]+dd;
}
}
}
if(flag)
puts("Yes");
else
puts("No");
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
u[x].push_back({y,z});
}
spfa();
}