depots depots numbered 0 to depots - 1, linked by two-way roads: roads[i] = [a, b, len] is a road of length len between depots a and b. Two depots may be linked by several roads. Right now every depot can be reached from every other one.
The company wants to close some depots (possibly none, possibly all). Roads leading to a closed depot go out of use too. After the closure, every remaining depot must still reach every other remaining depot over the remaining roads, with a shortest route no longer than reach.
Return the number of sets of closed depots for which this holds.depots=3, reach=4, roads=[[0, 1, 3], [1, 2, 3]] → 6
Keeping all three fails: depot 0 is 6 away from depot 2. Closing just 1 fails too, since 0 and 2 get cut off. Closing 0, closing 2, closing any two, or closing all three works: 6 sets in total.
depots=2, reach=5, roads=[[0, 1, 9], [0, 1, 2]] → 4
There are two roads between the depots; the short one takes 2, so all 4 closure sets work.
depots=1, reach=1, roads=[] → 2
depots ≤ 10reach ≤ 10⁵roads) ≤ 1000roads[i] = [a, b, len] with 0 ≤ a, b < depots and a ≠ bdepots=3, reach=4, roads=[[0, 1, 3], [1, 2, 3]]
6
Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.