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:
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
7005 Solvers
3266 Solvers
1562 Solvers
392 Solvers
Generate a vector like 1,2,2,3,3,3,4,4,4,4
2682 Solvers