You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

89 lines
2.8 KiB

2 years ago
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 5210 * 2;
int n, m1, m2;
int dist[N]; // dist[x]记录源点到x的最短距离
int cnt[N]; // cnt[x]记录源点到x在产生最短距离时的边数
bool st[N];
// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool spfa() {
// 初始化距离INF
memset(dist, 0x3f, sizeof dist);
// 是不是已经加入到集合中
memset(st, 0, sizeof st);
// 初始化从源点到x的最短距离时边数都是0
memset(cnt, 0, sizeof cnt);
queue<int> q;
// 底层相当于有一个虚拟源点0
// 0到 [1,n]的所有点边权为0不影响现在的图
// 从虚拟节点0出发到达所有的1~n就成为了单源最短路径问题
for (int i = 1; i <= n; i++) q.push(i), st[i] = true;
// spfa
while (q.size()) {
int u = q.front();
q.pop();
st[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dist[v] > dist[u] + w[i]) {
dist[v] = dist[u] + w[i];
/*
dist[j]jcnt[j]j
cnt[j] = cnt[u] + 1 ju + 1
jucnt[j] 1
cnt[j] >= n
cnt[j] >= n cntjnjn+1
n
*/
cnt[v] = cnt[u] + 1;
if (cnt[v] > n) return 1;
if (!st[v]) {
q.push(v);
st[v] = 1;
}
}
}
}
return 0;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m1, &m2);
// 初始化邻接表
memset(h, -1, sizeof h);
idx = 0;
int a, b, c;
// 田地 双向边
while (m1--) {
scanf("%d %d %d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
// 虫洞 回到t秒前 单向负边
while (m2--) {
scanf("%d %d %d", &a, &b, &c);
add(a, b, -c);
}
// 用spfa判断是不是有负环
spfa() ? puts("YES") : puts("NO");
}
return 0;
}