给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式 第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式 如果图中存在负权回路，则输出“Yes”，否则输出“No”。
数据范围 1≤n≤2000, 1≤m≤10000, 图中涉及边长绝对值均不超过10000。
输入样例： 3 3 1 2 -1 2 3 4 3 1 -4 输出样例： Yes
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int h[N],w[N],ne[N],idx,e[N]; int add(int a,int b,int c){ e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++; } int n,m,k; int dist[N],st[N],se[N];//dist 表示到i点的最小距离 st 标记数组 se 表示到i点 最小距离所走过的边数 int spfa(){ queue<int> q; for(int i=1;i<=n;i++){ q.push(i);st[i]=1; } while(q.size()){ int 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]; se[j]=se[t]+1;// 重点 到j点 最小距离更新加一 if(se[j]>=n) return -1;// 到某个点的边数大于等于了n 说明存在了负环 if(!st[j])q.push(j),st[j]=1; } } } return 0; } int main(){ cin>>n>>m; memset(h,-1,sizeof(h)); for(int i=0;i<m;i++){ int a,b,c;cin>>a>>b>>c; add(a,b,c); } int t=spfa(); if(t==-1) cout<<"Yes"; else cout<<"No"; return 0; }