AcWing 852. spfa判断负环(不需要初始化dist,默认为0,只有出现负边时才会更新)
原题链接
简单
作者:
半透明の微笑
,
2024-04-23 17:17:01
,
所有人可见
,
阅读 4
import java.io.*;
import java.util.*;
public class Main{
static int n, m;
static int N = 100010;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int idx;
static int[] dist = new int[N];
static int[] cnt = new int[N];
static boolean[] st = new boolean[N];
static PriorityQueue<Integer> q = new PriorityQueue<>();
static int INF = 0x3f3f3f3f;
static void spfa(){
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){
System.out.println("Yes");
return;
}
if(!st[j]){
q.add(j);
st[j] = true;
}
}
}
}
System.out.println("No");
}
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)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
Arrays.fill(h, -1);
for(int i = 0; i < m; i ++){
String[] s2 = br.readLine().split(" ");
int x = Integer.parseInt(s2[0]);
int y = Integer.parseInt(s2[1]);
int z = Integer.parseInt(s2[2]);
add(x, y ,z);
}
spfa();
}
}