题目重述与核心思路

我们有 $n$ 个变量，初始值为 $a_1,\dots,a_n$。有 $m$ 个操作，第 $i$ 个操作为 $(x_i, y_i, z_i)$，表示将 $x_i$ 赋值为 $\min(a_{x_i},\ a_{y_i}+z_i)$。

操作必须全部执行一次，但顺序任意。如果无论顺序如何，最终所有变量的值都相同，则初始序列是稳定的。若第 $i$ 个变量的最终值依赖于顺序，则序列是 $i$-不稳定的。

每个查询给出 $k$ 和初始 $a$，我们可以进行最多 $k$ 次操作，每次选择一个变量减 $1$。问：对每个 $i$，能否通过不超过 $k$ 次减 $1$ 操作，使序列变成 $i$-不稳定。

---

第一步：转化为图论问题

操作 $(x_i, y_i, z_i)$ 可以看作：
从 $y_i$ 到 $x_i$ 有一条有向边，权值为 $z_i$。
变量 $a_i$ 视为顶点 $i$ 的“初始距离”。

操作是松弛：
$\text{relax}(u \to v, w)$ 表示 $d_v = \min(d_v, d_u + w)$。

因此：

• 顶点 $1..n$，有向边 $y_i \to x_i$ 权 $z_i$。
• 初始距离 $a_i$。
• 按任意顺序对每条边恰好松弛一次。

这就像在图上跑单源最短路，但松弛顺序可以任意。

---

第二步：何时序列是 $i$-不稳定？

设 $d_{j,i}$ 为从 $j$ 到 $i$ 的最短路径长度（边数任意）。
设 $e_{j,i}$ 为从 $j$ 到 $i$ 的长度不超过 1 的路径（即 0 条边或 1 条边）的最短长度：

• 若 $j=i$，$e_{i,i} = 0$（0 条边）。
• 若存在 $j \to i$ 的边，则 $e_{j,i} = w(j,i)$。
• 否则 $e_{j,i} = +\infty$。

从 $j$ 出发到 $i$ 的真实最短距离为 $d_{j,i}$。
初始值 $a$ 相当于每个顶点 $j$ 有一个初始距离 $a_j$，那么顶点 $i$ 的最终可能值中，最小可能值是： [ \min_{j=1}^n (a_j + d_{j,i}) ] 因为可以先从 $j$ 出发沿最短路径走到 $i$。

如果所有最短路径长度 $\ge 2$（即路径至少包含 2 条边），那么 $d_{j,i} > e_{j,i}$ 对任意 $j$ 都不成立？
实际上，$i$-不稳定等价于： [ \min_{j} (a_j + d_{j,i}) < \min_{j} (a_j + e_{j,i}) ] 即使用多边路径能获得严格更小的值。
因为如果最短路径长度至少为 2，那么只用 0 或 1 条边的路径无法达到这个最小值，于是可以通过先松弛进入 $i$ 的边来“错过”这条最短路径，导致最终值更大。

结论：
序列是 $i$-不稳定 $\iff$ [ \min_j (a_j + d_{j,i}) < \min_j (a_j + e_{j,i}) ]

---

第三步：如何用减 $1$ 操作达成 $i$-不稳定？

我们只能减少 $a$ 的值。
减少 $a_j$ 会同时影响 $\min_j (a_j + d_{j,i})$ 和 $\min_j (a_j + e_{j,i})$。
目标：让前者小于后者。

对固定的 $i$，设： [ M_1 = \min_j (a_j + d_{j,i}) ] [ M_2 = \min_j (a_j + e_{j,i}) ] 初始时可能 $M_1 \ge M_2$。我们需要减少一些 $a_j$ 使得 $M_1 < M_2$。

关键观察：
要破坏平衡，我们应针对某个 $j$，使 $a_j + d_{j,i}$ 减小到比所有 $a_k + e_{k,i}$ 都小。
因为 $M_2$ 在减小时也会变，但 $M_1$ 可以减得更快。

更精确地：
我们想让 $a_j + d_{j,i}$ 成为新的最小值，并且它小于当前的 $M_2$。
设当前 $M_2$ 对应的顶点为 $t$（即 $a_t + e_{t,i} = M_2$），我们需要： [ a_j + d_{j,i} < a_t + e_{t,i} ] 如果 $d_{j,i} < e_{j,i}$（即 $j$ 到 $i$ 的最短路径长度 $\ge 2$），那么减少 $a_j$ 可以让左边变小，而 $a_t + e_{t,i}$ 不变（除非 $t=j$ 且 $e_{j,i}$ 也变，但 $e_{j,i}$ 固定）。

实际上，更通用的做法是：
我们考虑对每个顶点 $j$ 计算：为了使 $a_j + d_{j,i}$ 成为全局最小值，并且严格小于 $M_2$，需要减少 $a_j$ 多少。

设当前 $M_2 = m_2$。
我们希望： [ a_j' + d_{j,i} < m_2 ] 其中 $a_j' = a_j - t$，$t \ge 0$。
那么： [ a_j - t + d_{j,i} < m_2 ] [ t > a_j + d_{j,i} - m_2 ] 所以最小需要的减少次数为： [ \max(0, a_j + d_{j,i} - m_2 + 1) ] （因为要严格小于，所以 $+1$）

但这里假设 $M_2$ 在 $t$ 次减少后不变。实际上，如果 $j$ 恰好是 $M_2$ 的提供者，$m_2$ 也会变小。
所以更安全的方法是： [ \text{min_op}[i] = \min_{j: d_{j,i} < e_{j,i}} \left( (a_j + d_{j,i}) - (m_2 - 1) \right) ] 其中 $m_2 = \min_k (a_k + e_{k,i})$。
这个值就是需要减少的总次数，当减少次数达到它时，$a_j + d_{j,i}$ 会比原来的 $m_2$ 小 1，从而严格小于更新后的 $m_2$（因为 $m_2$ 最多也减少同样的量，但这里 $j$ 可能不同）。

---

第四步：算法流程

预处理：

1. 读入 $n,m$，建图 $e$（$e[x][y]$ 为 $x \to y$ 的最小权值，无则为 $+\infty$）。
2. 用 Floyd-Warshall 计算全源最短路 $d$（$n \le 500$，$O(n^3)$ 可行）。

每个查询：

输入 $k$ 和数组 $a$。
对每个顶点 $i$：

• 计算 $m_1 = \min_j (a_j + d_{j,i})$
• 计算 $m_2 = \min_j (a_j + e_{j,i})$
• 若 $m_1 < m_2$，则已 $i$-不稳定，需要 $0$ 次操作。
• 否则，计算： [ \text{need}i = \min{j: d_{j,i} < e_{j,i}} \left( a_j + d_{j,i} - (m_2 - 1) \right) ]
• 若 $\text{need}_i \le k$，则 $i$ 可变为不稳定。

输出长度为 $n$ 的 01 串。

---

第五步：复杂度

• 预处理：$O(n^3 + m)$
• 每个查询：$O(n^2)$（计算 $m_1,m_2$ 和遍历 $j$ 更新 need）
• $q \le 1000$，$n=500$，$n^2 = 2.5\times 10^5$，$q \cdot n^2 = 2.5\times 10^8$，在 C++ 优化下可过。

---

第六步：对照标程

标程中：

• e[i][j] 是单边最短距离（0 或 1 条边）
• d[i][j] 是任意最短距离
• min_dist 是 $m_1$（所有 $a_j + d_{j,i}$ 的最小值）
• min_one_edge 是 $m_2$（所有 $a_j + e_{j,i}$ 的最小值）
• min_op[i] 初始为无穷，对每个 $j$，如果 $d[j][i] < e[j][i]$，则更新： [ \text{min_op}[i] = \min(\text{min_op}[i],\ (d[j][i] + a[j]) - (\text{min_one_edge}[i] - 1)) ] 这与我们推导的 $\text{need}_i$ 一致。

最后输出 min_op[i] <= op。

---

第七步：示例验证

以第一个示例为例： $n=4$，$a=[20,0,15,5]$，$k=30$ 时输出 0110，表示变量 2、3 可变为不稳定。
这符合题意：需要减少 1 号变量 2 次，4 号变量 25 次，使得 $a_1=18, a_4=-20$，从而 $m_1 < m_2$ 对 $i=2,3$ 成立。

---

总结

本题的核心是：

1. 将操作视为图上的松弛，转化为最短路径问题。
2. $i$-不稳定等价于存在一条长度 $\ge 2$ 的最短路径比所有长度 $\le 1$ 的路径更优。
3. 通过减少 $a_j$ 使 $a_j + d_{j,i}$ 小于当前 $m_2$，所需次数可 $O(1)$ 计算。
4. 利用 Floyd-Warshall 预处理全源最短路，$O(n^3)$ 预处理，$O(n^2)$ 回答每个查询。