Problem J
A Feast For Cats
Your crazy aunt has asked you to watch her cats while she’s attending a seminar about making cat hats out of cat fur. Your aunt owns a great number of cats – all toms – and, due to the complex social structure of cats, every cat has a specific but different amount of hate reserved for every other cat.
Over the years, the cats have been spoiled to the point that they demand (at the least) $1$ milliliter of milk at tea time. Your task is to feed the cats the aforementioned milk, in order to dull their primal instincts and prevent an all-out cat war.
The task is complicated by three things:
-
Your aunt has a limited amount of milk stored in the fridge.
-
For each pair of cats, there is a distance they have to be kept from each other to avoid infighting.
-
The excessive amount of meowing has driven you to drink large amounts of hard liquor, and now you can’t move liquids without constant spilling. You will spill $1$ milliliter of the milk you carry for every meter you walk.
Given an amount of milk, and a set of cats – each pair of cats being a given distance apart from each other – determine if it’s possible to feed every cat at least $1$ milliliter of milk. Every cat has a cat bowl that can hold an arbitrary amount of milk. For every meter you walk, you will definitely spill $1$ milliliter of milk (instantly spoiling it), but instead of carrying all the milk at once, you may serve a cat more milk than needed and pick it up when backtracking (the cat will not drink the excess milk before you’re finished walking). The cats will never move, but they will eye each other with intense hate.
Input
The first line of the input consists of a single integer
$T$, the number of test
cases.
Each of the following $T$
cases begins with a line containing two positive integers
$M$ and $C$, separated by a space, denoting
the amount of milk in the fridge in milliliters and the number
of cats, respectively.
This is followed by $\frac{C
\cdot (C-1)}{2}$ (combinations of cats) lines containing
three positive integers $i$ $j$ $D_{i,j}$, separated by single spaces,
describing the distance between the cat with index $i$ and the cat with index
$j$ in meters. Cats are
numbered from $0$ up to
and including $C-1$, and
each pair of cats will be listed exactly once. You may assume
that the fridge is placed at the very same location as cat
$0$.
-
$1 \leq T \leq 20$
-
$1 \leq M \leq 20\, 000$
-
$1 \leq C \leq 2\, 000$
-
$1 \leq D_{i,j} \leq 3\, 000$
-
Cats co-exist in dimensions far greater than our three, so you can assume that every pair of cats is correctly separated by exactly the given distance.
Output
Output yes if it’s possible to serve every cat at least $1$ milliliter of milk. Output no if it’s not.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 20 5 0 1 4 0 2 3 0 3 10 0 4 15 1 2 7 1 3 3 1 4 5 2 3 4 2 4 3 3 4 8 |
yes |
