给定一张nn个点m条边的有向图，该图可以有自环与重边。

你需要判断从 1 号点出发，图中是否存在负权回路，存在输出 Yes；不存在输出 No。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static int N=2010;
    static int M=(int)1e4+10;
    static long INF=0x3f3f3f3f3f3f3f3fL;
    static int[]h=new int[N];
    static long[]dist=new long[N];
    static int[]e=new int[M*2],ne=new int[M*2];
    static int[]w=new int[M*2];
    static int[]cnt=new int[M*2];
    static boolean[]st=new boolean[N];
    static int idx,n,m;
    static void add(int a,int b,int c){
      e[idx]=b;
      w[idx]=c;
      ne[idx]=h[a];
      h[a]=idx++;
    }
    static boolean spfa(){
      Arrays.fill(st,false);
      Arrays.fill(dist,INF);
      dist[1]=0;
      Queue<Integer>q=new LinkedList<>();
      st[1]=true;
      q.offer(1);
      while(!q.isEmpty()){
        int t=q.poll();
        st[t]=false;
        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.offer(j);
              st[j]=true;
            }
          }
        }
      }
      return false;
    }
    static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        Arrays.fill(h,-1);
        String[]ss=in.readLine().split(" ");
        n=Integer.parseInt(ss[0]);
        m=Integer.parseInt(ss[1]);
        for(int i=1;i<=m;i++){
          String[]s=in.readLine().split(" ");
          int a=Integer.parseInt(s[0]);
          int b=Integer.parseInt(s[1]);
          int c=Integer.parseInt(s[2]);
          add(a,b,c);
        }
        if(spfa())System.out.println("Yes");
        else System.out.println("No");
    }
}