Problem H
Hide and Seek
Each round starts with Gloria hiding in one of the caves (except cave $0$) with uniform probability. Sven, starting in cave $0$, then has $n$ seconds to find Gloria. Each tunnel takes some number of seconds for Sven to traverse depending on the length of the tunnel, and can be traversed in both directions.
Sven likes to win, so he wants to choose his movements in such a way that he maximizes the probability of finding Gloria before the $n$ seconds are up. How many caves does Sven have time to visit?
Input
The input consists of:
-
one line with the integers $m$ and $n$ ($2 \le m \le 100$, $1 \le n \le 300$), the number of caves in the network and the number of seconds Sven has to find Gloria.
-
$m - 1$ lines with three integers $u$, $v$ and $t$ ($0 \le u \not= v < m$, $1 \le t \le 300$), the two endpoints of a tunnel and the time it takes to traverse the tunnel, in seconds.
Output
Output the maximum number of caves Sven can visit, excluding the cave he starts in.
| Sample Input 1 | Sample Output 1 |
|---|---|
11 50 0 1 5 1 2 4 1 3 9 0 4 6 4 5 6 5 6 3 0 7 8 7 8 10 7 9 5 9 10 2 |
6 |
