Jazzy Job
With the magnification of the Energy Crisis, Chemists have decided to re-examine the existing procedures of preparation of various Chemical Substances.
As part of this Project, they list all the elements that they commonly find as raw material (Initial Reactants), and the ones that they intend to produce (Final Products). They also prepar e an extensive list of the various known reactions/processes that are used to convert one substance to another.
One major issue that they find is that the Initiation of many reactions needs absurdly large amounts of energy. They wish to keep low the activation energies used in the new procedures.
Knowing all this, they now attempt to find out such methods of preparing the target substances :
(1) in which the highest value of activation energy needed by any of the reactions that make up the path, in any of the methods, does not exceed a given upper value,
(2) which minimizes the Total reactions/procedures performed in All the (Initial Reactant) --> (Final Product) conversions.
Each substance, on being given a specific amount of energy, converts into some other substance. The formed substance is unique for a particular value of Energy. The process of creating each successive Target Substance (Final Product) starts from one of the Source Substances Only, and leaves no by-products.
Your task is to find the minimum value of upper bound such that all final products are obtainable with that upper bound and for this minimum value, find out the minimum number of conversions to get all the final products.
Note: None of the procedures are Reversible, unless explicity stated. Also, if a procedure Is reversible, the Energy requirement may or may not be same. You may assume that there is a limitless supply of the Initial Reactants.
Input Desciption
The first line contains an integer t which is the number of test cases.
Each test case begins with a line containing three integers : number of Initial Reactants(S), Final Products(D) and the total number of elements (N). Then S+D lines follow, first S lines contain IDs of Initial reactant ( 0 based ) and next D lines contain ID's of Final products ( 0 based). Then follows a line containing an integer R which is number of reactions possible. Then follow R lines , each containing three integers , the Substance(S) , the converted substance(C) and the activation energy(A) units required for the reaction. 0 ≤ S,C < n.
Output Description
For each test case , output in a different line ,2 integers (a,b) separated by spaces where a is the minimum upper value and b is the minimum number of conversions required for corresponding a. In case that all final products are not obtainable for any value of upper bound, Print a single line with message "Excessive Energy.".
Sample Input
1
2 2 6
1
3
0
3
6
1 2 2
2 4 3
4 5 1
4 2 2
3 0 4
5 0 1
Sample Output
3 4
Constraints And Limits
Dataset 1: N ≤ 1000, S ≤ N,D ≤ N,R < 50000, 0 < A ≤ 100 Memory Limit: 128 MB. Time Limit: 3 sec. 50 points.
Dataset 2: N ≤ 10000, S ≤ N,D ≤ N,R < 100000 0 < A < 1000000000 Memory Limit: 128 MB. Time Limit: 3 sec. 100 points. Rank Team Name Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Score Penalty
1. MountainKing 100 200 150 150 300 200 - 250 0 150 1500 1020
2. evils 100 200 150 150 - 200 - 250 250 150 1450 1914
3. Kamikadze 100 200 150 150 - 200 0 250 0 150 1200 908
4. Excalibur 100 200 150 150 - 200 - 250 0 150 1200 1021
5. Arbiter 100 200 150 150 - 200 - 250 - 150 1200 1120
6. mary 100 200 150 150 - 200 - 250 - 150 1200 1221
7. TNU_Team1 100 200 150 150 - 200 0 250 - 150 1200 1414
8. GoogleKoalas 100 200 150 150 - 200 - 250 0 150 1200 1899
9. gawry 100 200 150 150 - 200 - 250 - 0 1050 986
10. StrictMath 100 200 0 150 - 200 - 250 - 150 1050 1217
Team Info : MountainKing
Members :Tiancheng Lou
Organisation :Tsinghua University
Country :CHINA 楼教主还是最厉害的~~~~~~~~~
页:
1
[2]