背景

请使用 C++ 20 提交。不要引入头文件，并在文件头粘贴如下内容：

#include <vector>
void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>);
void ReceiveA(bool);
std::vector<int> Answer();
void SendA(bool);
void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>);
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<int> U, std::vector<int> V, std::vector<int> 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<int> 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<int> S, std::vector<int> T, std::vector<int> 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，示例评测程序仅报告其中一种。

4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7

提示

数据范围

• $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 完成