## 题目描述这是一道通信题。有一张 $N$ 个点 $A+B$ 条边的带权无向图，点标号为 $0$ 到 $N-1$。其中 Azer 知道前 $A$ 条边的导出子图 $G_A$，Baijan 知道后 $B$ 条边的导出子图 $G_B$。它们之间可以互相传递一些 bit 的信息，求在原图上 $0$ 到所有点的最短路。 ## 通信格式只需提交一份代码。首先需要在代码开头包含头文件 `#include "transportations.h"`。然后需要实现以下函数： - `void InitA(int N, int A, std::vector U, std::vector V, std::vector C)` - 该函数只会在程序开始时执行一次。 - $N$ 表示原图的点数。 - $A$ 表示 $G_A$ 的边数。 - $\forall i \in [0,A)$，$(U_i,V_i,C_i)$ 表示图中一条连通 $U_i$ 与 $V_i$，长度为 $C_i$ 的无向边。 - `void ReceiveA(bool x)` - 表示接收来自 Baijan 的信息。 - 该函数在每次 `SendB(y)` 后将调用一次。 - 其 $x$ 取值与 $y$ 相等。 - `void SendA(bool y)` - 表示给 Baijan 发送一位信息。 - 你无需实现这个函数。 - `void InitB(int N, int B, std::vector S, std::vector T, std::vector D)` - 该函数只会在程序开始时执行一次。 - $N$ 表示原图的点数。 - $B$ 表示 $G_B$ 的边数。 - $\forall i \in [0,B)$，$(S_i,T_i,D_i)$ 表示图中一条连通 $S_i$ 与 $T_i$，长度为 $D_i$ 的无向边。 - `void ReceiveB(bool x)` - 表示接收来自 Azer 的信息。 - 该函数在每次 `SendA(y)` 后将调用一次。 - 其 $x$ 取值与 $y$ 相等。 - `void SendB(bool y)` - 表示给 Azer 发送一位信息。 - 你无需实现这个函数。 - `std::vector Answer()` - 表示提交答案。 - 在通信完成后调用一次。 - 需要返回一个长度为 $N$ 的 `std::vector` 类型，若长度不为 $N$，则会返回 **Wrong Answer [1]**。 - 其表示原图中 $0$ 到所有点的最短路长度。若你调用 `sendA` 与 `sendB` 的次数加起来超过 $58000$ 次，则会返回 **Wrong Answer [2]**。否则，下发的 grader 不会判断你的最短路是否正确，返回 Accepted: $L$，其中 $L$ 表示你调用的 `sendA` 和 `sendB` 次数之和。由于缺少赛时的 grader.cpp，所以本地无法看到返回的信息。 ## 数据范围 | 子任务编号 | $N$ | 特殊性质 | 分数 | | :--------: | :--------: | :----------: | :--: | | 1 | | $A=0$ | 6 | | 2 | | $B \le 1000$ | 8 | | 3 | | $A+B=N-1$ | 8 | | 4 | $\le 900$ | | 38 | | 5 | $\le 1100$ | | 14 | | 6 | $\le 1400$ | | 10 | | 7 | $\le 2000$ | | 16 | 对于 $100\%$ 的数据，满足： - $1 \le N \le 2000$ - $0 \le A,B \le 5 \times 10^5$ - $\forall i \in [0,A)$，$0 \le U_i,V_i \le N-1$，$U_i \ne V_i$ - $\forall 0 \le x < y

AT_joisc2019_f ふたつの交通機関 (Two Transportations)

题目描述

输入格式

输出格式

说明/提示