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 R2-D2 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, R2-D2 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 R2-D2 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 R2-D2 to reach planet $y$ or determine that it is impossible to reach planet $y$ for any $L$. Note that the level R2-D2 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 space-separated integers $N$ and $M$. - The second line contains $N$ space-separated 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 R2-D2 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 space-separated 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, R2-D2 can travel through planets $1 \rightarrow 3 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$.
|Tags||disjoint-set, farhod_farmon, ltime71, medium-hard, sorting, taran_1407, tree-based|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.