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
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers15
Suggested Problems
-
3646 Solvers
-
Find state names that end with the letter A
1173 Solvers
-
2971 Solvers
-
1296 Solvers
-
20992 Solvers
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!