P3385 【Template】Negative Cycle

Given a directed graph with $n$ vertices, determine whether there exists a negative cycle that is **reachable from vertex $1$**. A negative cycle is defined as a cycle whose sum of edge weights is negative.

This problem contains multiple groups of testdata in a single test point. The first line contains an integer $T$, representing the number of groups of testdata. For each group, the format is as follows: The first line contains two integers, the number of vertices $n$ and the number of lines $m$ of edge information that follow. Then follow $m$ lines, each with three integers $u, v, w$. - If $w \geq 0$, then there exists an edge from $u$ to $v$ with weight $w$, and also an edge from $v$ to $u$ with weight $w$. - If $w < 0$, then there exists only an edge from $u$ to $v$ with weight $w$.

For each group of testdata, output one line containing a string. Print `YES` if such a negative cycle exists, otherwise print `NO`.

#### Constraints and Conventions For all test points, it is guaranteed that: - $1 \leq n \leq 2 \times 10^3$, $1 \leq m \leq 3 \times 10^3$. - $1 \leq u, v \leq n$, $-10^4 \leq w \leq 10^4$. - $1 \leq T \leq 10$. #### Hint Please note that $m$ is **not** the number of edges of the graph. Translated by ChatGPT 5