77 lines
1.8 KiB
Java
77 lines
1.8 KiB
Java
import java.util.*;
|
|
|
|
class Node {
|
|
int u, v, w;
|
|
|
|
Node(int u, int v, int w) {
|
|
this.u = u;
|
|
this.v = v;
|
|
this.w = w;
|
|
}
|
|
}
|
|
|
|
class _1865 {
|
|
|
|
static boolean bellman_ford(Node[] edges, Node info) {
|
|
int N = info.u;
|
|
int M = info.v;
|
|
int W = info.w;
|
|
|
|
int[] distance = new int[N+1];
|
|
Arrays.fill(distance, 0);
|
|
|
|
for(int n=0; n<N; n++) {
|
|
for(int i=0; i<2*M+W; i++) {
|
|
int current = edges[i].u;
|
|
int next = edges[i].v;
|
|
int time = edges[i].w;
|
|
|
|
if(distance[next] > distance[current] + time) {
|
|
if(n==N-1) return true;
|
|
|
|
distance[next] = distance[current] + time;
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
|
|
Scanner sc = new Scanner(System.in);
|
|
int T = sc.nextInt();
|
|
|
|
for(int t=0; t<T; t++) {
|
|
int N = sc.nextInt();
|
|
int M = sc.nextInt();
|
|
int W = sc.nextInt();
|
|
Node info = new Node(N, M, W);
|
|
|
|
Node[] edges = new Node[2*M+W];
|
|
|
|
for(int i=0; i<2*M; i+=2) {
|
|
int u = sc.nextInt();
|
|
int v = sc.nextInt();
|
|
int w = sc.nextInt();
|
|
|
|
edges[i] = new Node(u, v, w);
|
|
edges[i+1] = new Node(v, u, w);
|
|
}
|
|
|
|
for(int i=0; i<W; i++) {
|
|
int u = sc.nextInt();
|
|
int v = sc.nextInt();
|
|
int w = sc.nextInt();
|
|
|
|
edges[2*M+i] = new Node(u, v, (-1)*w);
|
|
}
|
|
|
|
boolean negative_cycle = bellman_ford(edges, info);
|
|
|
|
System.out.println(negative_cycle ? "YES" : "NO");
|
|
}
|
|
|
|
sc.close();
|
|
}
|
|
} |