Make him The Ultimate
All submissions for this problem are available.Shivam is playing the new Ben-10 game called "Make him The Ultimate". But its way too tough for him, so he has come to you to help him out. The game is described as follows - Ben-10 has grown up , and become Ben-N. Bokalaka has captured Gwen and Grandpa. Ben is in his ith alien form , and to defeat Bokalaka , he has to transform in jth form(The Ultimate form). At every transformation , he can **change** his watch battery , and then its battery level will become Xi and it will cost him Ci Health Points.(*He can also choose not to change the battery and will continue with his previous battery*). **The Battery is Changed, not Charged** Also to make a transition from one form to another it takes Zi battery charge, i.e he can only transform to other form only if he have the required charge in battery. ***Note that , there can be more than one way to make the same transition.*** Now Shivam wants your help to find the minimum amount of Health Points BEN-N needs to become the Ultimate Alien and save Gwen and Grandpa. If there is no way to achive that transformation , output -1. ***Initialy Watch is at zero charge.*** ###Input: The first line contains N(Number of Alien Transformation Ben Have) , M(Number of fesible transformation) , A(Initial Form) , B(Ultimate Form). Next M lines contains 3 interger X , Y , Z each , showing from Xth form he can transform in Yth form and the required Charge Z. Next N lines contains 2 interger each , Ci , Hi, that means , at ith form , he can Change his watch's battery having Charge Ci with decrease in Health Point of Hi. ###Output: Single Line Cointaing Minimum Health Points needed to transform form Initial Form to the Ultimate Form. ###Constraints 1 ≤ N ≤ 1000 0 ≤ M ≤ 1000 1 ≤ Inital_Form , Ultimate_Form ≤ N 1 ≤ Xi , Yi ≤ N 1 ≤ Zi ≤ 109 1 ≤ Ci , Hi ≤ 109 ###Sample Input: 3 3 1 3 1 2 2 1 3 3 3 2 1 2 7 2 7 3 6 ###Sample Output: 14
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.