AcWing 852. spfa判断负环-java
原题链接
简单
作者:
Susu
,
2020-01-30 13:59:47
,
所有人可见
,
阅读 728
import java.util.*;
public class Main {
static int N = 10010;//边数M
static int n,m;
static int idx;
static int[] h = new int[N];
static int[] w = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] cnt = new int[N];
static int[] dist = new int[N]; //用于记录每一个点距离第一个点的距离
static boolean[] st = new boolean[N];//用于记录该点的最短距离是否已经确定
static boolean spfa(){
Queue<Integer> q = new LinkedList<>();
for(int i=1;i<=n;i++){
q.add(i);
st[i]=true;
}
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.add(j);
st[j]=true;
}
}
}
}
return false;
}
static void add(int a,int b,int c){
e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=0;i<N;i++){
h[i]=-1;
}
while(m-->0){
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
add(x,y,z);
}
if(spfa()) System.out.print("Yes");
else System.out.print("No");
}
}