P11350 [NOISG 2024 Finals] Shops

Yuland 是一个由 $n$ 个城市组成的小镇，城市之间通过 $m$ 条双向道路连接，每条道路有不同的长度。从任何城市可以通过道路到达其他城市，可能存在多条道路连接相同的城市对。 每个城市可以建造一个兔子店或鸭子店，但不能同时建造两者。每个城市的居民希望能够收集到这两种动物。一个城市的不便程度定义为距离最近的兔子店和距离最近的鸭子店的距离之间的最大值。 你需要帮助 Yuland 的市长决定在每个城市建造哪种店铺，以最小化所有城市中的最大不便程度。

- 第一行包含两个整数 $n$ 和 $m$，分别表示城市数量和道路数量。 - 接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$，表示一条连接城市 $u_i$ 和 $v_i$ 的双向道路，其长度为 $w_i$。

- 第一行输出一个整数，表示最小可能的不便程度的最大值。 - 第二行输出一个由 $n$ 个字符组成的字符串，其中第 $i$ 个字符表示第 $i$ 个城市建造的店铺类型： - `B` 表示兔子店。 - `D` 表示鸭子店。 - 如果有多个满足条件的方案，可以输出任意一个。

【样例解释】 对于样例 #1： - 城市 $1$ 和 $2$ 建造兔子店，城市 $3$ 建造鸭子店。 - 对于城市 $1$，到最近的鸭子店的距离为 $2$，到最近的兔子店的距离为 $0$。 - 对于城市 $2$，到最近的兔子店和鸭子店的距离均为 $1$。 - 对于城市 $3$，到最近的兔子店的距离为 $1$，到最近的鸭子店的距离为 $0$。 - 最大不便程度为 $2$。 对于样例 #2： - 城市建造的店铺类型为 `DBDDB`，最大不便程度为 $9$。 【数据范围】 - $2 \leq n, m \leq 500,000$ - $1 \leq u_i, v_i \leq n$ - $1 \leq w_i \leq 10^9$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $0$ | $0$ | 样例测试用例 | | $1$ | $7$ | $n \leq 16$ | | $2$ | $13$ | $m = n-1$ 且 $u_i = i, v_i = i+1$ | | $3$ | $18$ | $m = n-1$ | | $4$ | $24$ | $w_i = 1$ | | $5$ | $38$ | 无额外限制 |