AcWing 852. spfa判断负环-java
原题链接
简单
作者:
Astarion
,
2021-02-15 16:36:39
,
所有人可见
,
阅读 275
import java.io.*;
import java.util.Arrays;
class Main {
static final int INF = 0x3fffffff;
static int n, m;
//稀疏图,邻接表存储
static int idx;
static int[] h = new int[2100];
static int[] e = new int[10010];
static int[] ne = new int[10010];
static int[] w = new int[10010];
//spfa队列
//由于会多次入队,长度设为n*m
static int[] queue = new int[21000000];
static int head, tail;
static boolean[] isIn = new boolean[2100];
//用于记录从某点到另一点的最短路经过的边数
static int[] cnt = new int[2100];
//存储两点间的最短路
static int[] dist = new int[2100];
static {
Arrays.fill(h, -1);
}
static void insert(int a, int b, int v) {
e[idx] = b;
w[idx] = v;
ne[idx] = h[a];
h[a] = idx++;
}
static boolean spfa() {
//全部顶点入队
for (int i = 1; i <= n; i++) {
queue[tail++] = i;
isIn[i] = true;
}
while (head < tail) {
int t = queue[head++];
isIn[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int a = e[i];
if (dist[a] > dist[t] + w[i]) {
dist[a] = dist[t] + w[i];
cnt[a] = cnt[t] + 1;
if (cnt[a] == n) return false;
if (!isIn[a]) {
queue[tail++] = a;
isIn[a] = true;
}
}
}
}
return true;
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
for (int i = 0; i < m; i++) {
strs = in.readLine().split(" ");
int a = Integer.parseInt(strs[0]);
int b = Integer.parseInt(strs[1]);
int v = Integer.parseInt(strs[2]);
insert(a, b, v);
}
in.close();
isr.close();
OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter out = new BufferedWriter(osw);
if (spfa()) out.write("No");
else out.write("Yes");
out.flush();
out.close();
osw.close();
}
}