Problem 45467. Find the fastest reaction chain to reach a target compound

This problem is related to Problem 45470.

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 and a target compound T, can you find a reaction chain between them with the smallest total completion time?

The inputs to this problem are R, S, and T. 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 total time of the fastest reaction chain from S to T, rounded to 2 decimal places. If a solution does not exist, then output Inf. You are ensured that:

• 2 <= N <= 20
• S, T, and all elements in the first 2 columns of R are integers within [1, N].
• Completion times are decimal numbers within (0,10].
• S is not equal to T.
• 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_chain(R,1,4)
ans = 
     6.20