CF2112F Variables and Operations

有 $n$ 个变量，记第 $i$ 个变量的值为 $a_i$。 还有 $m$ 个操作将会应用于这些变量，第 $i$ 个操作由三个整数 $x_i, y_i, z_i$ 描述。当应用第 $i$ 个操作时，变量 $x_i$ 会被赋值为：$\min(a_{x_i}, a_{y_i} + z_i)$。 每个操作都会被恰好应用一次，但它们的顺序不固定，可以以任意顺序应用。 如果对于任意操作顺序，最终变量的值都相同，则称初始变量值序列 $a_1, a_2, \dots, a_n$ 是稳定的。如果第 $i$ 个变量的最终值依赖于操作顺序，则称该初始变量值序列是 $i$-不稳定的。 你需要处理 $q$ 个询问。每个询问会给出初始变量值 $a_1, a_2, \dots, a_n$ 和一个整数 $k$。在应用操作之前，你最多可以选择 $k$ 次，将某个变量的值减少 $1$。对于每个变量 $i$，你需要独立判断是否有可能通过不超过 $k$ 次的减少操作，使得该序列变成 $i$-不稳定的。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500$，$1 \le m \le 4 \cdot 10^5$），分别表示变量个数和操作个数。 接下来 $m$ 行，每行包含三个整数 $x_i, y_i, z_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$，$0 \le z_i \le 10^5$），表示第 $i$ 个操作的描述。 接下来一行包含一个整数 $q$（$1 \le q \le 1000$），表示询问个数。 每个询问包含两行： - 第一行包含一个整数 $k$（$0 \le k \le 10^9$），表示你最多可以进行的减少操作次数； - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），表示变量的初始值。

对于每个询问，输出一个由 $n$ 个 $0$ 和 $1$ 组成的字符串。第 $i$ 个字符为 $1$ 表示有可能得到 $i$-不稳定的序列，否则为 $0$。

考虑第一个样例。如果初始变量值为 $[20, 0, 15, 5]$，无论操作顺序如何，最终变量值都为 $[6, 0, 5, 5]$。减少变量 $10$ 次还不够。然而，如果最多可以进行 $30$ 次减少操作，我们可以将第 $1$ 个变量减少 $2$，第 $4$ 个变量减少 $25$，得到初始值 $[18, 0, 15, -20]$，此时该序列是 $2$-不稳定和 $3$-不稳定的： - 如果按给定顺序应用操作，最终得到 $[-12, 0, 5, -20]$； - 如果按顺序 $[3, 2, 4, 1, 5]$ 应用操作，最终得到 $[-12, -2, 5, -20]$； - 如果按顺序 $[3, 4, 5, 1, 2]$ 应用操作，最终得到 $[-12, -2, 3, -20]$。 由 ChatGPT 4.1 翻译