CF1851G Vlad and the Mountains

Vlad 决定去山里旅行。他计划在 $n$ 座山之间移动，其中有些山之间通过道路相连。第 $i$ 座山的高度为 $h_i$。 如果山 $i$ 和山 $j$ 之间有道路，Vlad 可以从山 $i$ 移动到山 $j$，这将消耗 $h_j - h_i$ 单位的能量。如果在移动过程中能量降到零以下，他将无法从山 $i$ 移动到山 $j$。注意，$h_j - h_i$ 可能为负数，这时能量会恢复。 Vlad 想要考虑不同的路线选择，因此他请你回答以下查询：给定他初始有 $e$ 单位能量，是否存在一条从山 $a$ 出发到达山 $b$ 的路线？

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le \min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$），分别表示山的数量和道路的数量。 第二行包含 $n$ 个整数 $h_1, h_2, h_3, \dots, h_n$（$1 \le h_i \le 10^9$），表示每座山的高度。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示第 $u$ 座山和第 $v$ 座山之间有一条道路。保证没有重复的道路。 接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示查询的数量。 接下来的 $q$ 行，每行包含三个整数 $a$、$b$ 和 $e$（$1 \le a, b \le n$，$0 \le e \le 10^9$），分别表示路线的起点、终点和初始能量。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 和 $q$ 的总和也不超过 $2 \cdot 10^5$。

对于每个查询，如果 Vlad 能够从山 $a$ 出发到达山 $b$，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案）。 在下面的示例中，不同测试用例的答案之间用空行分隔，你不需要输出空行。

由 ChatGPT 4.1 翻译