Professor on a Trip

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME74/hindi/PROFTRIP.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME74/bengali/PROFTRIP.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME74/mandarin/PROFTRIP.pdf), [Russian](http://www.codechef.com/download/translated/LTIME74/russian/PROFTRIP.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME74/vietnamese/PROFTRIP.pdf) as well. The Professor is going on a trip with his family this weekend. The country where they live is a federation of $N$ states (numbered $1$ through $N$) with $R$ bidirectional interstate roads connecting them. For each road, we know the amount of fuel the Professor needs to traverse it; travelling within a state consumes no fuel. For each $i$, the price of fuel in state $i$ is fixed at $F_i$ units of money per litre. Despite Professor's outstanding talent and his great scientific prowess, he has some bad habits as well: he is too pennywise, so he carries huge barrels in his car in order to store extra petrol and avoid buying petrol in expensive states. Therefore, he is able to carry any amount of fuel he wants at any moment during the trip, and he is also fine with visiting the same state more than once on the trip if it saves him money. The Professor starts the trip without any fuel. Help the Professor find the minimum possible amount of money he should spend on fuel in order to travel from state $P$ to state $Q$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $R$.  Each of the next $R$ lines contains three spaceseparated integers $u$, $v$ and $w$ denoting that states $u$ and $v$ are connected by a road and it takes $w$ litres of fuel to traverse that road.  The next line contains $N$ spaceseparated integers $F_1, F_2, \ldots, F_N$.  The next line contains two spaceseparated integers $P$ and $Q$. ### Output For each test case, print a single line containing one integer ― the minimum amount of money the Professor has to spend. ### Constraints  $1 \le T \le 5$  $1 \le N \le 300$  $1 \le R \le N \cdot (N  1) / 2$  $1 \le u, v, P, Q \le N$  each road connects two different states  no two roads connect the same pair of states  $1 \le w \le 10^6$  $1 \le F_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (40 points):** $N \le 50$ **Subtask #2 (60 points):** original constraints ### Example Input ``` 1 4 3 1 2 3 2 3 1 2 4 7 3 6 2 2 1 4 ``` ### Example Output ``` 28 ``` ### Explanation **Example case 1:** The Professor can buy $10$ litres of petrol in state $1$, travel to state $2$ and then to state $4$. This way, he spends $30$ units of money. However, the optimal solution is to buy $4$ litres of petrol in state $1$, travel to state $2$, then to state $3$, buy $8$ litres of petrol in state $3$ and then travel to state $4$, since this costs only $28$ units of money.Author:  erfaniaa 
Editorial  https://discuss.codechef.com/problems/PROFTRIP 
Tags  dynamicprogramming, erfaniaa, floydwarshall, ltime74, shortestpath 
Date Added:  24072019 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 