All submissions for this problem are available.You are given a graph with $N$ nodes and $M$ edges. Each edge has a value associated with it. There are no self-loops and multiple edges in the graph. Each edge connects two nodes. The cost of going from the first node of the edge to the second via the edge is equal to the value of the edge whereas the cost of going in the reverse direction is equal to the negative of it. Your task is to figure out if the graph is conservative or not. A graph is conservative if and only if for each pair of nodes, the cost of reaching the one node from the other is the same via all possible paths. The cost of a path is simply the sum of the costs of each edge in the path. ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase contains $M+1$ lines of input. - The first line contains the integers $N$ and $M$. - The next $M$ lines contain the description of the edges. Each line contains the integers $u$ $v$ $w$ denoting that an edge exists between the nodes $u$ and $v$ with the value $w$. - It is guaranteed that if there is an edge between $u$ to $v$ then there will be no edge from $v$ to $u$. ###Output: For each testcase, output "YES" if the graph is conservative otherwise "NO" ###Constraints - $1 \leq T \leq 10^5$ - $1 \leq N \leq 10^5$ - $1 \leq M \leq min(10^5,(N*(N-1))/2)$ - $1 \leq u,v \leq N$ - $-10^9 \leq w \leq 10^9$ - The sum of $N$ over all testcases is less than equal to $10^6$. - The sum of $M$ over all testcases is less than or equal to $10^6$. ###Sample Input: 2 4 4 1 2 2 2 3 1 4 1 -1 3 4 -2 4 4 1 2 2 2 3 2 1 4 2 4 3 1 ###Sample Output: YES NO ###EXPLANATION: In the second testcase, the path $1->2->3$ has cost $4$ while the path $1->4->3$ has cost $3$
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.