The Last Droid

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME71/hindi/R2D2.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME71/bengali/R2D2.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME71/mandarin/R2D2.pdf), [Russian](http://www.codechef.com/download/translated/LTIME71/russian/R2D2.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME71/vietnamese/R2D2.pdf) as well. The droid R2D2 is travelling in space with a special mission. In space, there are $N$ planets (numbered $1$ through $N$) and $M$ bidirectional space highways. Each space highway connects two planets and in order to use it, R2D2 needs to have a sufficiently high *status level*. The droid’s mission consists of $Q$ stages. In each stage, there are two planets $x$ and $y$ such that the droid should start the stage at planet $x$ with some initial status level $L$ ($L \ge 0$) and travel to planet $y$. For each valid $i$, when R2D2 is at planet $i$ (including the initial planet $x$), he may increase his status level by $A_i$; it is not allowed to increase the status level multiple times on the same planet in the same stage. Find the minimum value of $L$ such that it is possible for R2D2 to reach planet $y$ or determine that it is impossible to reach planet $y$ for any $L$. Note that the level R2D2 has at the end of each stage is not carried over to the next stages (he may start the next stage with a lower initial status level). ### 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 $M$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  Each of the following $M$ lines contains three space separated integers $U$, $V$ and $W$ denoting that there is a space highway between planets $U$ and $V$ and R2D2 may use this highway only if his status level is at least $W$.  The next line contains a single integer $Q$.  The following $Q$ lines describe stages. Each of these lines contains two spaceseparated integers $x$ and $y$. ### Output For each stage, print a single line containing one integer ― the minimum status level required to complete the stage, or $1$ if it is impossible to complete this stage. ### Constraints  $1 \le T \le 100$  $1 \le N, M, Q \le 10^5$  $0 \le A_i \le 10^9$ for each valid $i$  $0 \le W \le 10^9$  $1 \le U, V, x, y \le N$  the sum of $N$ over all test cases does not exceed $400,000$  the sum of $M$ over all test cases does not exceed $400,000$  the sum of $Q$ over all test cases does not exceed $400,000$ ### Subtasks **Subtask #1 (12 points):**  $N, Q \le 1,000$  $M \le 1,200$  the sum of $N$ over all test cases does not exceed $4,000$  the sum of $M$ over all test cases does not exceed $4,000$  the sum of $Q$ over all test cases does not exceed $4,000$ **Subtask #2 (28 points):** $A_i = 0$ for each valid $i$ **Subtask #3 (60 points):** original constraints ### Example Input ``` 1 6 5 1 3 1 2 0 0 1 2 4 1 3 2 1 4 3 3 4 5 3 5 7 4 2 2 1 5 5 1 3 6 ``` ### Example Output ``` 0 1 7 1 ``` ### Explanation In the second stage, R2D2 can travel through planets $1 \rightarrow 3 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$.Author:  farhod_farmon 
Editorial  https://discuss.codechef.com/problems/R2D2 
Tags  disjointset, farhod_farmon, ltime71, mediumhard, sorting, taran_1407, treebased 
Date Added:  25042019 
Time Limit:  4 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