Modi In Biksy
All submissions for this problem are available.
Modi visits Biksy, the largest trading market in the land. Biksy has traders from all over the world.
There are a total of N items indexed from 1 to N, that are traded in the market by a total of M dealers. Each trader is characterized by three integers, say i, j, C , meaning that the trader will take i'th item from you and give you j'th item and C units of money. A negative value of C signifies that, in order to get j'th item from the trader, you will have to give i'th item and C units of money. Note that there can be multiple dealers who deal with the same pair of items and some crazy dealers might trade the same item as well i.e. (i = j).
Modi visits Biksy having the item number 1. He collects the data of all the traders and wants to know if there is way by which he can become infinity rich if he acts smart! i.e. if there are a series of profits, repeating which, will always increase the number of units of money with him! Help Modi find the answer to this question. Note that Monk can go to any dealer any number of times.
First line contains an integer T. T test cases follow.
First line of each test case contains two space-separated integers N, M
Next M lines contain three space-separated integers i, j and C, the characteristics of the traders.
Print "Yes"(without the quotes) if such a way exists, "No"(without the quotes) otherwise.
Print the answer to each test case in a new line.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 1000
- 1 ≤ i,j ≤ N
- -1000 ≤ C ≤ 1000
Input: 2 5 6 1 2 2 2 3 -1 3 4 -7 4 5 0 2 3 -7 3 5 6 5 8 1 5 10 2 3 -6 5 2 5 4 5 9 1 5 1 2 4 -10 2 3 -2 4 1 1 Output: No Yes
For the first test case, there is no such way possible.
For the second test case, Monk starts with item 1.
Trades it for 5th item gaining 10 units.
Trades 5th for 2nd gaining 5 units.
Trades 2nd for 4th losing 10 units.
Trades 4th for 1st gaining 1 unit.
Thereby, gaining 6 units in this process and it can be repeated indefinitely to make Monk infinitely rich!
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.