310561: CF1851G. Vlad and the Mountains
Description
Vlad decided to go on a trip to the mountains. He plans to move between $n$ mountains, some of which are connected by roads. The $i$-th mountain has a height of $h_i$.
If there is a road between mountains $i$ and $j$, Vlad can move from mountain $i$ to mountain $j$ by spending $h_j - h_i$ units of energy. If his energy drops below zero during the transition, he will not be able to move from mountain $i$ to mountain $j$. Note that $h_j - h_i$ can be negative and then the energy will be restored.
Vlad wants to consider different route options, so he asks you to answer the following queries: is it possible to construct some route starting at mountain $a$ and ending at mountain $b$, given that he initially has $e$ units of energy?
InputThe first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The descriptions of the test cases follow.
The first line of each test case contains two numbers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$) — the number of mountains and the number of roads between them, respectively.
The second line contains $n$ integers $h_1, h_2, h_3, \dots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the mountains.
The next $m$ lines contain two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — the numbers of the mountains connected by a road. It is guaranteed that no road appears twice.
The next line contains an integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.
The following $q$ lines contain three numbers $a$, $b$, and $e$ ($1 \le a, b \le n$, $0 \le e \le 10^9$) — the initial and final mountains of the route, and the amount of energy, respectively.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. The same guarantee applies to $m$ and $q$.
OutputFor each query, output "YES" if Vlad can construct a route from mountain $a$ to mountain $b$, and "NO" otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).
In the examples below, the answers for different test cases are separated by an empty line, which you do not need to output.
ExamplesInput2 7 7 1 5 3 4 2 4 1 1 4 4 3 3 6 3 2 2 5 5 6 5 7 5 1 1 3 6 2 0 4 7 0 1 7 4 1 7 2 6 5 4 7 6 2 5 1 1 3 5 3 1 5 2 4 6 2 5 1 5 1 1 3 1 1 2 1000 6 2 6 6 2 5Output
YES NO YES YES NO YES NO NO YES NOInput
2 3 2 1 3 9 1 2 2 3 5 1 1 1 3 2 2 1 1 2 3 3 0 1 2 1 3 3 1 4 1 1 2 2 3 1 3 5 3 3 9 1 3 6 1 1 2 3 3 6 3 3 4Output
YES YES YES YES NO YES YES YES YES YESInput
1 6 10 7 9 2 10 8 6 4 2 6 1 4 5 3 5 6 4 1 3 2 6 6 5 1 2 3 6 5 4 4 8 3 3 1 5 5 9 2 1 7 6 6 10Output
YES YES YES YES YES
Input
Output
Vlad决定去山上旅行。他计划在n座山之间移动,其中一些山通过道路相连。第i座山的高度为h_i。
如果第i座山和第j座山之间有道路,Vlad可以通过消耗h_j - h_i单位的能量从第i座山移动到第j座山。如果他在过渡期间能量下降到零以下,他将无法从第i座山移动到第j座山。注意,h_j - h_i可以是负数,此时能量将得到恢复。
Vlad想要考虑不同的路线选项,所以他请你回答以下查询:在初始有e单位能量的情况下,是否可以构造从山a开始到山b结束的路线?
**输入数据格式:**
第一行包含一个整数t(1 ≤ t ≤ 10^4)——测试用例的数量。
接下来是t个测试用例的描述。
每个测试用例的第一行包含两个数字n和m(2 ≤ n ≤ 2 * 10^5,1 ≤ m ≤ min(n(n - 1)/2, 2 * 10^5))——山的数量和山之间的道路数量。
第二行包含n个整数h_1, h_2, h_3, …, h_n(1 ≤ h_i ≤ 10^9)——山的高度。
接下来的m行每行包含两个整数u和v(1 ≤ u, v ≤ n,u ≠ v)——通过道路连接的山编号。保证没有重复的道路。
接下来一行包含一个整数q(1 ≤ q ≤ 2 * 10^5)——查询的数量。
接下来的q行每行包含三个数字a、b和e(1 ≤ a, b ≤ n,0 ≤ e ≤ 10^9)——路线的初始和最终山以及能量数量。
**输出数据格式:**
对于每个查询,如果Vlad可以构造从山a到山b的路线,输出“YES”,否则输出“NO”。
输出答案时大小写不敏感,即“yEs”、“yes”、“Yes”和“YES”都会被视为肯定答案。
测试用例之间输出的答案用空行分隔,但你不需输出这些空行。**题目大意:** Vlad决定去山上旅行。他计划在n座山之间移动,其中一些山通过道路相连。第i座山的高度为h_i。 如果第i座山和第j座山之间有道路,Vlad可以通过消耗h_j - h_i单位的能量从第i座山移动到第j座山。如果他在过渡期间能量下降到零以下,他将无法从第i座山移动到第j座山。注意,h_j - h_i可以是负数,此时能量将得到恢复。 Vlad想要考虑不同的路线选项,所以他请你回答以下查询:在初始有e单位能量的情况下,是否可以构造从山a开始到山b结束的路线? **输入数据格式:** 第一行包含一个整数t(1 ≤ t ≤ 10^4)——测试用例的数量。 接下来是t个测试用例的描述。 每个测试用例的第一行包含两个数字n和m(2 ≤ n ≤ 2 * 10^5,1 ≤ m ≤ min(n(n - 1)/2, 2 * 10^5))——山的数量和山之间的道路数量。 第二行包含n个整数h_1, h_2, h_3, …, h_n(1 ≤ h_i ≤ 10^9)——山的高度。 接下来的m行每行包含两个整数u和v(1 ≤ u, v ≤ n,u ≠ v)——通过道路连接的山编号。保证没有重复的道路。 接下来一行包含一个整数q(1 ≤ q ≤ 2 * 10^5)——查询的数量。 接下来的q行每行包含三个数字a、b和e(1 ≤ a, b ≤ n,0 ≤ e ≤ 10^9)——路线的初始和最终山以及能量数量。 **输出数据格式:** 对于每个查询,如果Vlad可以构造从山a到山b的路线,输出“YES”,否则输出“NO”。 输出答案时大小写不敏感,即“yEs”、“yes”、“Yes”和“YES”都会被视为肯定答案。 测试用例之间输出的答案用空行分隔,但你不需输出这些空行。