P14345 [JOISC 2019] 两种交通 / Two Transportations

**请使用 C++ 20 提交**。不要引入头文件，并在文件头粘贴如下内容： ```cpp #include void InitA(int, int, std::vector, std::vector, std::vector); void ReceiveA(bool); std::vector Answer(); void SendA(bool); void InitB(int, int, std::vector, std::vector, std::vector); void ReceiveB(bool); void SendB(bool); ```

JOI 国有 $N$ 座城市，编号从 $0$ 到 $N-1$。有 $A$ 条铁路线，编号从 $0$ 到 $A-1$。铁路线 $i$（$0 \le i \le A-1$）双向连接城市 $U_i$ 与城市 $V_i$，票价为 $C_i$。不同的铁路线连接不同的城市对。另有 $B$ 条公交线路，编号从 $0$ 到 $B-1$。公交线路 $j$（$0 \le j \le B-1$）双向连接城市 $S_j$ 与城市 $T_j$，票价为 $D_j$。不同的公交线路连接不同的城市对，但一条铁路线与一条公交线路可能连接相同的城市对。通过铁路和/或公交，可以在任意两座城市之间通行。 Azer 想知道从城市 $0$ 到每个城市的最小总票价。由于 Azer 仅了解铁路线的信息，他与仅了解公交线路信息的 Baijan 合作。 他们通过发送和接收字符 0 或 1 进行通信。发送的字符总数应小于或等于 58000。 编写程序，Azer 的程序接收铁路线信息，Baijan 的程序接收公交线路信息，二者通过通信协作，帮助 Azer 找到从城市 $0$ 到每个城市的最小总票价。 ### 实现细节 你需要实现两个文件。 第一个文件的名称为 `Azer.cpp`。它表示 Azer 的行为，应实现以下函数。该文件应包含 `Azer.h`。 - `void InitA(int N, int A, std::vector U, std::vector V, std::vector C)` 此函数在程序开始时恰好执行一次。 - 参数 $N$ 是城市数量 $N$。 - 参数 $A$ 是铁路线数量 $A$。 - 参数 $U$、$V$ 是长度为 $A$ 的数组。$U[i]$ 和 $V[i]$ 是由铁路线 $i$（$0 \le i \le A-1$）连接的两座城市。 - 参数 $C$ 是长度为 $A$ 的数组。$C[i]$ 是铁路线 $i$（$0 \le i \le A-1$）的票价 $C_i$。 - `void ReceiveA(bool x)` 此函数在 Baijan 每发送一个字符时执行一次。 - 参数 $x$ 表示 Baijan 发送的字符：`true` 代表字符 1，`false` 代表字符 0。 - `std::vector Answer()` 此函数在所有发送的字符均被接收后恰好执行一次。该函数必须返回一个数组 $Z$，其中包含从城市 $0$ 到每个城市的最小总票价。 - 返回值 $Z$ 必须是一个长度为 $N$ 的数组。若其长度不为 $N$，你的程序将被判定为 **Wrong Answer [1]**。 - $Z[k]$（$0 \le k \le N-1$）必须是从城市 $0$ 到城市 $k$ 所需的最小总票价。特别地，需满足 $Z[0] = 0$。 你的程序可在本文件中调用以下函数： - `void SendA(bool y)` 使用此函数向 Baijan 发送一个字符。 - 参数 $y$ 表示要发送给 Baijan 的字符：`true` 代表字符 1，`false` 代表字符 0。 第二个文件的名称为 `Baijan.cpp`。它表示 Baijan 的行为，应实现以下函数。该文件应包含 `Baijan.h`。 - `void InitB(int N, int B, std::vector S, std::vector T, std::vector D)` 此函数在程序开始时恰好执行一次。 - 参数 $N$ 是城市数量 $N$。 - 参数 $B$ 是公交线路数量 $B$。 - 参数 $S$、$T$ 是长度为 $B$ 的数组。$S[j]$ 和 $T[j]$ 是由公交线路 $j$（$0 \le j \le B-1$）连接的两座城市 $S_j$ 与 $T_j$。 - 参数 $D$ 是长度为 $B$ 的数组。$D[j]$ 是公交线路 $j$（$0 \le j \le B-1$）的票价 $D_j$。 - `void ReceiveB(bool y)` 此函数在 Azer 每发送一个字符时执行一次。 - 参数 $y$ 表示 Azer 发送的字符：`true` 代表字符 1，`false` 代表字符 0。 你的程序可在本文件中调用以下函数： - `void SendB(bool x)` 使用此函数向 Azer 发送一个字符。 - 参数 $x$ 表示要发送给 Azer 的字符：`true` 代表字符 1，`false` 代表字符 0。 你可以假设程序按如下方式执行。对于每个测试用例，准备两个队列：$Q_Y$，用于存储 Azer 发送的字符；以及 $Q_X$，用于存储 Baijan 发送的字符。首先，执行 `InitA` 和 `InitB`，并将发送的字符推入对应的队列。 - 若 $Q_X$ 或 $Q_Y$ 非空，则从其中一个队列中弹出一个字符，并执行对应的 `ReceiveA` 或 `ReceiveB`。然而，若 $Q_X$ 与 $Q_Y$ 均非空，则无法确定执行 `ReceiveA` 还是 `ReceiveB`。 - 当在 `ReceiveA` 执行期间调用 `SendA` 时，所发送的字符将被推入 $Q_Y$。 - 当在 `ReceiveB` 执行期间调用 `SendB` 时，所发送的字符将被推入 $Q_X$。 - 若两个队列均为空，则执行 `Answer`，程序结束。 Azer 与 Baijan 发送的字符总数应小于或等于 58000。若超过该限制，你的程序将被判定为 **Wrong Answer [2]**。 ### 重要提示 - 你的程序可为内部用途实现其他函数，或使用全局变量。提交的文件将与评测程序一起编译，生成一个可执行文件。所有全局变量与内部函数应声明于一个未命名命名空间中，以避免与其他文件冲突。在评测时，程序将作为 Azer 与 Baijan 两个独立进程运行。Azer 进程与 Baijan 进程不能共享全局变量。 - 你的程序不应使用标准输入与标准输出。你的程序不应以任何方式与其他文件通信。然而，你的程序可向标准错误输出调试信息。

示例评测程序从标准输入读取如下格式的数据： $N\ A\ B$ $U_0\ V_0\ C_0$ $\vdots$ $U_{A-1}\ V_{A-1}\ C_{A-1}$ $S_0\ T_0\ D_0$ $\vdots$ $S_{B-1}\ T_{B-1}\ D_{B-1}$

示例评测程序将以下信息写入标准输出和标准错误（为清晰起见，此处使用引号）： - 若你的程序被判定为 **Wrong Answer [1]** 或 **Wrong Answer [2]**，它会将类型写作 “Wrong Answer [1]” 输出至标准错误，且不会向标准输出写入任何内容。 - 否则，它会将发送字符的总数 $L$ 以 “Accepted: L” 的形式写入标准错误。同时，它会按以下格式将你的答案 $Z$ 写入标准输出： $Z[0]$ $\vdots$ $Z[N - 1]$ 示例评测程序不会检查 $Z$ 的值是否正确。 若你的程序被判定为多种类型的 **Wrong Answer**，示例评测程序仅报告其中一种。

### 数据范围 - $1 \le N \le 2000$。 - $0 \le A \le 500000$。 - $0 \le B \le 500000$。 - $0 \le U_i \le N - 1$（$0 \le i \le A - 1$）。 - $0 \le V_i \le N - 1$（$0 \le i \le A - 1$）。 - $U_i \ne V_i$（$0 \le i \le A - 1$）。 - $(U_{i_1}, V_{i_1}) \ne (U_{i_2}, V_{i_2})$ 且 $(U_{i_1}, V_{i_1}) \ne (V_{i_2}, U_{i_2})$（$0 \le i_1 < i_2 \le A - 1$）。 - $0 \le S_j \le N - 1$（$0 \le j \le B - 1$）。 - $0 \le T_j \le N - 1$（$0 \le j \le B - 1$）。 - $S_j \ne T_j$（$0 \le j \le B - 1$）。 - $(S_{j_1}, T_{j_1}) \ne (S_{j_2}, T_{j_2})$ 且 $(S_{j_1}, T_{j_1}) \ne (T_{j_2}, S_{j_2})$（$0 \le j_1 < j_2 \le B - 1$）。 - 任意两座城市之间均可通过铁路和/或公交线路到达。 - $1 \le C_i \le 500$（$0 \le i \le A - 1$）。 - $1 \le D_j \le 500$（$0 \le j \le B - 1$）。 ### 子任务 1. （6 分）$A = 0$。 2. （8 分）$B \le 1000$。 3. （8 分）$A + B = N - 1$。 4. （38 分）$N \le 900$。 5. （14 分）$N \le 1100$。 6. （10 分）$N \le 1400$。 7. （16 分）无额外约束。 翻译由 Qwen3-235B 完成