Problem 45470. Count the number of reaction chains achievable in T mins

This problem is related to Problem 45467.

Let's denote a list of N compounds as 1, 2, ..., N. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --> 2), as well as the time it takes to complete them ( completion time ). With this information, we can generate reaction chains. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:

Given N = 4 and the following valid reactions:
Reaction 1:    1 --> 2 takes 1.5 mins
Reaction 2:    1 --> 3 takes 2.5 mins 
Reaction 3:    2 --> 3 takes 0.6 mins
Reaction 4:    3 --> 4 takes 4.1 mins 
Reaction 5:    4 --> 2 takes 3.2 mins
Sample reaction chains: 1 --> 3 --> 4         takes (2.5 + 4.1) mins
                        1 --> 2 --> 3 --> 4   takes (1.5 + 0.6 + 4.1) mins 
                        4 --> 2 --> 3         takes (3.2 + 0.6) mins

Note that conversion reactions can only move forward. But if the list states that converting to and from the same two compounds is possible, then a reaction chain can take only one of these paths.

Your task is this: Given a starting compound S, can you count how many reaction chains are possible whose total completion time does not exceed T mins?

Note that if multiple valid reaction steps are possible between two compounds (e.g. "1 --> 2 takes 1.5 mins" and "1 --> 2 takes 2.5 mins" both appear in the list), then reaction chains that take either of these paths are distinct. Lastly, for this problem, reaction chains must not contain duplicate compounds; otherwise, they become "cycles" rather than "chains".

The inputs to this problem are R, S, and T. The meanings of S and T are given above. Variable R is a 3-column matrix containing the list of valid reaction steps at each row i:

"Reaction i: R( i, 1) --> R( i, 2) takes R( i, 3) mins"

Output the required number of reaction chains. You are ensured that:

• N and T are integers satisfying: 2 <= N <= 20 and 1 <= T <= 100.
• S and all elements in the first 2 columns of R are integers within [1, N].
• Completion times are decimal numbers within (0,10].
• Each compound 1, ..., N is mentioned at least once in R. Hence, N can be inferred from matrix R.

The following sample test case is the one illustrated above:

>> R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];
>> reaction_chain2(R,1,5)
ans = 
     3
>> reaction_chain2(R,1,10)
ans = 
     6

In this example, all the reaction chains starting from Compound 1 are:

(1.50 mins) 1 --> 2
(2.10 mins) 1 --> 2 --> 3
(6.20 mins) 1 --> 2 --> 3 --> 4
(2.50 mins) 1 --> 3
(6.60 mins) 1 --> 3 --> 4
(9.80 mins) 1 --> 3 --> 4 --> 2