1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <bits/stdc++.h> using namespace std;
#define maxn 1000000 int T, n, m; int to[maxn], edge[maxn], head[maxn], Next[maxn], cnt; int dist[maxn]; bool visit[maxn]; int num[maxn]; queue<int> q; void add(int x, int y, int z) { to[++cnt] = y, edge[cnt] = z, Next[cnt] = head[x], head[x] = cnt; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while (T--) { bool flag = false; memset(visit, 0, sizeof(visit)); memset(dist, 0x3f, sizeof(dist)); memset(num, 0, sizeof(num)); memset(head, 0, sizeof(head)); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; if (w >= 0) { add(u, v, w); add(v, u, w); } if (w < 0) { add(u, v, w); } } dist[1] = 0, visit[1] = 1; q.push(1); while (q.empty() == false) { int x = q.front(); q.pop(); visit[x] = 0; for (int i = head[x]; i; i = Next[i]) { int y = to[i], z = edge[i]; if (dist[y] > dist[x] + z) { dist[y] = dist[x] + z; num[y] = num[x] + 1; if (num[y] >= n) { flag = true; break; } if (!visit[y]) q.push(y), visit[y] = true; } } } if (flag) cout << "YES" << endl; else cout << "NO" << endl; }
return 0; }
|