// y总的原话
// 每次做一遍spfa()一定是正确的,但时间复杂度较高,可能会超时。初始时将所有点插入队列中可以按如下方式理解:
// 在原图的基础上新建一个虚拟源点,从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa,将虚拟源点加入队列中。然后进行spfa的第一次迭代,这时会将所有点的距离更新并将所有点插入队列中。执行到这一步,就等价于视频中的做法了。那么视频中的做法可以找到负环,等价于这次spfa可以找到负环,等价于新图有负环,等价于原图有负环。得证。
// 1、dist[x] 记录虚拟源点到x的最短距离
// 2、cnt[x] 记录当前x点到虚拟源点最短路的边数,初始每个点到虚拟源点的距离为0,只要他能再走n步,即cnt[x] >= n,则表示该图中一定存在负环,由于从虚拟源点到x至少经过n条边时,则说明图中至少有n + 1个点,表示一定有点是重复使用
// 3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少,因此进行对该点j进行更新,并且对应cnt[j] = cnt[t] + 1,往前走一步
// 注意:该题是判断是否存在负环,并非判断是否存在从1开始的负环,因此需要将所有的点都加入队列中,更新周围的点
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 2010, M = 10010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int d[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa()
{
queue<int> q;
for(int i = 1; i <= n; i ++ ) q.push(i), st[i] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i], cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) q.push(j), st[j] = true;
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset (h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa() ? puts("Yes") : puts("No");
return 0;
}