CF1515G Phoenix and Odometers

在 Fire City，有 $n$ 个路口和 $m$ 条单向道路。第 $i$ 条道路从路口 $a_i$ 通往 $b_i$，长度为 $l_i$ 英里。 有 $q$ 辆只能沿这些道路行驶的汽车。第 $i$ 辆车从路口 $v_i$ 出发，其里程表初始为 $s_i$，每行驶一英里增加 $1$，当达到 $t_i$ 时归零（重置为 $0$）。Phoenix 的任务是驾驶每辆车沿若干条道路（可以为零条）行驶，并回到其起始路口，使得里程表显示为 $0$。 对于每辆车，请判断是否存在这样的行驶方案。 一辆车可以多次经过同一条道路或路口。里程表在重置后会继续计数，因此可以被重置任意多次。

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$；$1 \le m \le 2 \cdot 10^5$），分别表示路口数和道路数。 接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $l_i$（$1 \le a_i, b_i \le n$；$a_i \neq b_i$；$1 \le l_i \le 10^9$），表示第 $i$ 条道路的信息。图不一定连通。保证任意两个路口之间，每个方向最多只有一条道路。 接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示汽车数量。 接下来的 $q$ 行，每行包含三个整数 $v_i$、$s_i$ 和 $t_i$（$1 \le v_i \le n$；$0 \le s_i < t_i \le 10^9$），分别表示第 $i$ 辆车的起始路口、里程表初始数字和重置数字。

输出 $q$ 行答案。如果第 $i$ 辆车可以通过行驶若干条道路（可以为零条）并回到起始路口 $v_i$，使得里程表显示为 $0$，则输出 YES，否则输出 NO。

第一个样例的示意图如下：  对于第一个询问，Phoenix 可以按如下路线行驶：$1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1$。里程表会被重置 $3$ 次，但最后显示为 $0$。 对于第二个询问，可以证明没有办法让里程表归零并回到路口 $1$。 对于第三个询问，里程表本身已经是 $0$，无需行驶任何道路。 第二个样例的示意图如下：  由 ChatGPT 4.1 翻译