P10434 [JOIST 2024] 间谍 3 / Spy 3
题目背景
在本题中，你需要将两个文件合并成一个文件提交。
**不要引入任何头文件**，并在文件头加入如下的内容：
```cpp
#include
void answer(const std::vector &);
```
题目描述
Aoi 和 Bitaro 是 JOI 国 国家情报局的间谍。这次他们的任务是对 IOI 国 进行潜入调查。Bitaro 潜入 IOI 国，而 Aoi 在 JOI 国 向 Bitaro 发出指示。
潜入前，Aoi 和 Bitaro 得到了 IOI 国 的一张地图。IOI 国 有 $N$ 个城市，编号为 $0$ 到 $N-1$。此外，IOI 国 有 $M$ 条道路，编号为 $0$ 到 $M-1$。第 $i$ 条道路（$0 \le i \le M-1$）双向连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。通过若干条道路可以在任意两座城市之间往来。Bitaro 在 IOI 国 内通过这些道路在城市间移动。另外，共有 $Q$ 个调查计划。第 $j$ 个计划（$0 \le j \le Q-1$）要调查 IOI 国 的城市 $T_j$。
以上信息最初同时告知了 Aoi 和 Bitaro。随后，Bitaro 开始潜入 IOI 国。
Bitaro 设法甩开了无数追兵，击败了刺客，最终成功潜入 IOI 国 的城市 $0$。然而，由于潜入行动极其艰难，Bitaro 遗失了关于 IOI 国 的部分信息。具体而言，Bitaro 丢失了 $K$ 条道路的长度信息，即道路 $X_0, X_1, \dots, X_{K-1}$。换言之，Bitaro 已不知道 $C_{X_0}, C_{X_1}, \dots, C_{X_{K-1}}$ 的数值。注意，尽管 Bitaro 丢失了这些信息，Aoi 仍然掌握它们。
Bitaro 立刻向 Aoi 报告了他所遗失的道路长度信息是哪些。
为了完成任务，Bitaro 希望从城市 $0$ 出发，分别找到到每个被 $Q$ 个调查计划锁定的城市的最短路径。
Aoi 将向 Bitaro 发送一个只包含字符 ‘0’ 或 ‘1’ 的字符串以协助他。由于存在被截获的风险，Aoi 希望尽量减少发送的内容。
给定关于 IOI 国 的信息、调查计划以及 Bitaro 所遗失信息的道路，请编写程序实现 Aoi 的发送策略；同时，编写程序实现 Bitaro 在其掌握的信息与 Aoi 发送的字符串下寻找最短路径的策略。
### 实现细节
你需要提交 $2$ 个文件。
第一个文件为 `Aoi.cpp`。该文件用于实现 Aoi 的策略，并应实现以下函数。程序需通过预处理指令 `#include` 包含 `Aoi.h`。
* `std::string aoi(int N, int M, int Q, int K, std::vector A, std::vector B, std::vector C, std::vector T, std::vector X)`
此函数在每个测试用例中只被调用一次。
* 参数 $N$ 是 IOI 国 中的城市数量。
* 参数 $M$ 是 IOI 国 中的道路数量。
* 参数 $Q$ 是调查计划的数量。
* 参数 $K$ 是 Bitaro 遗失长度信息的道路条数。
* 参数 $A, B, C$ 为长度为 $M$ 的数组。表示第 $i$ 条道路（$0 \le i \le M-1$）双向连接城市 $A[i]$ 与城市 $B[i]$，长度为 $C[i]$。
* 参数 $T$ 为长度为 $Q$ 的数组。表示第 $j$ 个计划（$0 \le j \le Q-1$）要调查的城市为 $T[j]$。
* 参数 $X$ 为长度为 $K$ 的数组。表示 Bitaro 遗失长度信息的道路为 $X[0], X[1], \dots, X[K-1]$。
* 返回值为 Aoi 向 Bitaro 发送的字符串 $s$。
* 字符串 $s$ 的每个字符必须是 ‘0’ 或 ‘1’。若不满足此条件，你的程序将被判定为 **Wrong Answer [1]**。
* 字符串 $s$ 的长度最多为 $12000$。若不满足此条件，你的程序将被判定为 **Wrong Answer [2]**。
第二个文件为 `Bitaro.cpp`。该文件用于实现 Bitaro 的策略，并应实现以下函数。程序需通过预处理指令 `#include` 包含 `Bitaro.h`。
* `void bitaro(int N, int M, int Q, int K, std::vector A, std::vector B, std::vector C, std::vector T, std::vector X, std::string s)`
此函数会在 `aoi` 函数被调用之后且仅被调用一次。
* 参数 $N$ 是 IOI 国 中的城市数量。
* 参数 $M$ 是 IOI 国 中的道路数量。
* 参数 $Q$ 是调查计划的数量。
* 参数 $K$ 是 Bitaro 遗失长度信息的道路条数。
* 参数 $A, B, C$ 为长度为 $M$ 的数组。表示第 $i$ 条道路（$0 \le i \le M-1$）双向连接城市 $A[i]$ 与城市 $B[i]$，长度为 $C[i]$。
* 参数 $T$ 为长度为 $Q$ 的数组。表示第 $j$ 个计划（$0 \le j \le Q-1$）要调查的城市为 $T[j]$。
* 参数 $X$ 为长度为 $K$ 的数组。表示 Bitaro 遗失长度信息的道路为 $X[0], X[1], \dots, X[K-1]$。
* 参数 $s$ 是一个每个字符均为 ‘0’ 或 ‘1’ 的字符串，表示 Aoi 发送给 Bitaro 的字符串。
在 `Bitaro.cpp` 中，你的程序可以调用如下函数。
```cpp
void answer(const std::vector &e)
```
* 在第 $(j+1)$ 次调用（$0 \le j \le Q-1$）该函数时，你需要回答从城市 $0$ 到第 $j$ 个调查计划目标城市 $T_j$ 的最短路径。
* 参数 `e` 是一个数组，表示从城市 $0$ 到城市 $T_j$ 的最短路径所经过的道路序列。
* 设数组 `e` 的长度为 $n$。元素 `e[0], e[1], \ldots, e[n-1]` 是该最短路径上按行进顺序经过的道路的编号。
* 若存在多条最短路径，任选其一作为答案即可。
* 参数 `e` 的每个元素必须在 $0$ 到 $M-1$ 之间。若不满足此条件，你的程序将被判定为 **Wrong Answer [3]**。
* 参数 `e` 所指示的道路序列必须构成一条从城市 $0$ 到城市 $T_j$ 的路径。更正式地，它必须满足以下条件。
* 存在一列数字 $u_0, u_1, \ldots, u_n$ 使得
* $u_0 = 0$。
* $u_n = T_j$。
* 道路 $e[k]$（$0 \le k \le n-1$）连接城市 $u_k$ 与城市 $u_{k+1}$。
* 若不满足这些条件，你的程序将被判定为 **Wrong Answer [4]**。
* 若参数 `e` 指示的道路序列并非所有从城市 $0$ 到城市 $T_j$ 的路径中长度最短的一条，你的程序将被判定为 **Wrong Answer [5]**。这里，路径长度定义为所用道路长度之和。
* 函数 `answer` 必须被调用恰好 $Q$ 次。若在 `bitaro` 函数结束时，对 `answer` 的调用次数不等于 $Q$，你的程序将被判定为 **Wrong Answer [6]**。
### 重要注意事项
* 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的文件将与评测程序一起编译，形成单个可执行文件。所有全局变量与内部函数应声明在未命名命名空间中，以避免与其他文件冲突。评测时会分别以 Aoi 进程与 Bitaro 进程运行。Aoi 进程与 Bitaro 进程不能共享全局变量。
* 你的程序不得使用标准输入与标准输出。你的程序不得以任何方式与其他文件通信。但你可以向标准错误输出调试信息。
### 编译与测试运行
你可以从比赛网页下载包含样例评测器的压缩包，用于本地测试。压缩包中也包含你程序的样例源文件。
样例评测器文件为 `grader.cpp`。为测试你的程序，请将 `grader.cpp`、`Aoi.cpp`、`Bitaro.cpp`、`Aoi.h`、`Bitaro.h` 放在同一目录下，并运行以下命令进行编译。你也可以运行压缩包内的 `compile.sh`。
```bash
g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp
```
当编译成功时，将生成可执行文件 `grader`。
注意，实际评测器不同于样例评测器。样例评测器作为单进程执行，从标准输入读取数据，并向标准输出与标准错误输出写出结果。
输入格式
样例评测器从标准输入读取如下数据。
> $N$ $M$\
> $A_0$ $B_0$ $C_0$\
> $A_1$ $B_1$ $C_1$\
> $A_{M-1}$ $B_{M-1}$ $C_{M-1}$\
> $Q$\
> $T_0$ $T_1$ $\cdots$ $T_{Q-1}$\
> $K$\
> $X_0$ $X_1$ $\cdots$ $X_{K-1}$
输出格式
样例评测器向标准输出与标准错误输出输出如下信息（引号仅为说明）。
* 若你的程序被判为 **Wrong Answer [1], [2], [3], [4], 或 [6]**，样例评测器会在标准错误输出写出其类型，如 “Wrong Answer [1]”。标准输出不会输出任何内容。
* 否则，`aoi` 函数返回的字符串 $s$ 的长度会以 “Accepted: 2024” 的格式输出到标准错误输出。此外，在第 $(j+1)$ 次（$0 \le j \le Q-1$）对 `answer` 的调用中，路径长度会输出到标准输出的第 $(j+1)$ 行。样例评测程序 **不会检查** 该路径是否最短。
若你的程序同时满足多种 Wrong Answer 的条件，样例评测器仅报告其中一种。
说明/提示
### 示例通信
下面给出一个样例评测器的输入及相应的函数调用。
| 样例输入 1 | 调用 | 返回值 |
|---|---|---|
| $$\texttt{3 3}\\ \texttt{1 2 1} \\ \texttt{0 2 2} \\ \texttt{0 1 3} \\ \texttt{2} \\ \texttt{2 1} \\ \texttt{2} \\ \texttt{0 1}$$ | `aoi(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [1, 2, 3], [2, 1], [0, 1])` | |
| ^ | | `"101001"` |
| ^ | `bitaro(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [-1, -1, 3], [2, 1], [0, 1], "101001")` | |
| ^ | `answer([1])` | |
| ^ | `answer([1, 0])` | |
从城市 $0$ 到城市 $1$ 的最短路径，可以按顺序经过道路 $1$ 和 $0$，或者仅经过道路 $2$。因此，在本样例的第二次对 `answer` 的调用中，调用 `answer([2])` 也是可以接受的。
从比赛网站下载的文件 `sample-01-in.txt` 与输入样例 $1$ 相对应。压缩包中的 `sample-01-in.txt` 与 `sample-02-in.txt` 可作为样例评测器的输入。
### 约束
所有输入数据均满足以下条件：
* $2 \le N \le 10000$。
* $1 \le M \le 20000$。
* $1 \le Q \le 16$。
* $1 \le K \le 300$。
* $0 \le A_i < B_i \le N-1$（$0 \le i \le M-1$）。
* $(A_i, B_i) \ne (A_j, B_j)$（$0 \le i < j \le M-1$）。
* $1 \le C_i \le 10^{12}$（$0 \le i \le M-1$）。
* $1 \le T_j \le N-1$（$0 \le j \le Q-1$）。
* $T_j \ne T_k$（$0 \le j < k \le Q-1$）。
* $0 \le X_k \le M-1$（$0 \le k \le K-1$）。
* $X_k \ne X_l$（$0 \le k < l \le K-1$）。
* 通过若干条道路可以在任意两座城市之间往来。
* 所有输入值均为整数。
### 评分
若你的程序在任意测试用例中被判定为 **Wrong Answer [1] - [6]**（见实现细节）或出现任意类型的运行时错误（TLE、MLE、异常结束等），你的得分为 $0$ 分。
否则，评分依据为在本题所有测试用例中，函数 `aoi` 返回的字符串 $s$ 的最大长度 $L$。
* 若 $1561 \le L \le 12000$，得分为 $\left\lfloor \dfrac{100\,000}{L-560} \right\rfloor$。
* 若 $0 \le L \le 1560$，得分为 $100$ 分。
其中，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。