This is a classical problem in graph theory, namely the detection of negative-weight cycles. It can be solved using the Bellman-Ford algorithm. Bellman-Ford is a shortest-path algorithm, which is slower than Dijkstra but handles graphs with negative edge lengths. It works by storing the best known time to reach each pasture and repeatedly updating these times. In each pass, every edge is examined, and the time required to reach the endpoint of the edge is updated if necessary. This is repeated until the times stabilise and there are no further changes to be made. If there are no negative-weight cycles, then the times stabilise within N passes (because that is the most possible edges in a shortest path). If a negative-weight cycle is reached, the times will never stabilise.
Thus, we can run Bellman-Ford for N iterations, and if the times have still not stabilised then we have a negative-weight cycle. The only question is where to start: if we start in the wrong place, we might not reach a negative-weight cycle, even if it exists. The solution is simple: start everywhere at once, i.e., set the initial earliest-time to zero for every pasture. That this is valid can be shown rigorously, but this is left as an exercise.
#include <fstream> #include <algorithm> using namespace std; int main() { int F, N, M, W; ifstream in("wormhole.in"); ofstream out("wormhole.out"); in >> F; for (int f = 0; f < F; f++) { int A[6000], B[6000], T[6000], P = 0; bool cycle = false; int dist[500]; in >> N >> M >> W; memset(dist, 0, sizeof(dist)); for (int i = 0; i < M; i++) { in >> A[P] >> B[P] >> T[P]; A[P]--; B[P]--; A[P + 1] = B[P]; B[P + 1] = A[P]; T[P + 1] = T[P]; P += 2; } for (int i = 0; i < W; i++) { in >> A[P] >> B[P] >> T[P]; A[P]--; B[P]--; T[P] = -T[P]; P++; } for (int r = 0; r <= N; r++) for (int i = 0; i < P; i++) dist[B[i]] <?= dist[A[i]] + T[i]; for (int i = 0; i < P; i++) if (dist[B[i]] > dist[A[i]] + T[i]) cycle = true; out << (cycle ? "YES\n" : "NO\n"); } return 0; }