[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1715
[算法]
用SPFA判定负环是否存在即可
时间复杂度 ： O(N ^ 2)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 500010 const int inf = 2e9; struct edge { int to , w , nxt; } e[MAXN]; int n , m , p , tot; int head[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; } inline bool spfa() { static int dist[MAXN] , cnt[MAXN]; static bool inq[MAXN]; queue< int > q; for (int i = 1; i <= n; i++) { cnt[i] = 0; dist[i] = inf; inq[i] = false; } cnt[1] = 1; dist[1] = 0; q.push(1); while (!q.empty()) { int cur = q.front(); q.pop(); inq[cur] = false; for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (dist[cur] + w < dist[v]) { dist[v] = dist[cur] + w; if (!inq[v]) { inq[v] = true; if (++cnt[v] > n) return true; q.push(v); } } } } return false; } int main() { int T; read(T); while (T--) { read(n); read(m); read(p); tot = 0; for (int i = 1; i <= n; i++) head[i] = 0; for (int i = 1; i <= m; i++) { int u , v , w; read(u); read(v); read(w); addedge(u , v , w); addedge(v , u , w); } for (int i = 1; i <= p; i++) { int u , v , w; read(u); read(v); read(w); addedge(u , v , -w); } if (spfa()) printf("YES "); else printf("NO "); } return 0; }