← 返回题目列表

Codeforces · 2077/G

G. RGB行走

中文机器翻译题面 查看原题
红、蓝、绿 - fn 和 Silentroom
⠀

给您一个连通图,其中包含 $$$n$$$ 个顶点和 $$$m$$$ 双向边,权重不超过 $$$x$$$。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$,权重为 $$$w_i$$$,并指定颜色 $$$c_i$$$ ($$$1 \leq i \leq m$$$, $$$1 \leq u_i, v_i \leq n$$$)。颜色 $$$c_i$$$ 是红色、绿色或蓝色。保证有 至少 每种颜色的一个边缘。

对于顶点和边可能重复的行走,令 $$$s_r、s_g、s_b$$$ 分别表示该行走经过的红、绿、蓝边的权重之和。如果一条边被多次遍历,则每次遍历都单独计数。

求从顶点 $$$1$$$ 到顶点 $$$n$$$ 的所有可能路径中 $$$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$$$ 的最小值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$x$$$ ($$$4 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \leq x \leq 2 \cdot 10^5$$$) — 分别是图中的顶点数、边数以及边权重的上限。

接下来的 $$$m$$$ 行每行包含三个整数 $$$u_i, v_i, w_i$$$ 和一个字母 $$$c_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq w_i \leq x$$$),表示顶点 $$$u_i$$$ 和$$$v_i$$$ 重量为 $$$w_i$$$ 和颜色 $$$c_i$$$。颜色 $$$c_i$$$ 是“r”、“g”或“b”,分别表示红色、绿色和蓝色。

保证图是连通的并且至少包含每种颜色的一条边。该图还可能包含 多个 边缘和 自循环.

此外,保证所有测试用例中 $$$n$$$ 的所有值的总和、$$$m$$$ 的所有值的总和以及 $$$x$$$ 的所有值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 从顶点 $$$1$$$ 到顶点 $$$n$$$ 的所有行走中 $$$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$$$ 的最小值。

示例

输入
复制

3
4 3 3
1 2 2 r
2 3 3 g
3 4 2 b
4 5 4
1 2 1 r
1 1 1 r
2 1 1 r
2 3 4 g
3 4 4 b
4 6 4
1 2 2 r
1 2 2 r
2 3 3 b
1 3 4 r
1 4 1 g
3 4 4 g

输出
复制

1
0
0

注意

在第一个测试用例中,最佳路径是 $$$1 \to 2 \to 3 \to 4$$$。使用的边是:

  • $$$1 \to 2$$$ (红色,重量 $$$2$$$)
  • $$$2 \to 3$$$ (绿色,重量 $$$3$$$)
  • $$$3 \到 4$$$ (蓝色,重量 $$$2$$$)

我们有 $$$s_r = 2$$$、$$$s_g = 3$$$ 和 $$$s_b = 2$$$。因此,答案是$$$1$$$。

在第二个测试用例中,最佳路径之一是 $$$1 \to 1 \to 2 \to 1 \to 2 \to 3 \to 4$$$。使用的边是:

  • $$$1 \to 1$$$ (红色,重量 $$$1$$$)
  • $$$1 \到 2$$$ (红色,重量 $$$1$$$)
  • $$$2 \to 1$$$ (红色,重量 $$$1$$$)
  • $$$1 \到 2$$$ (红色,重量 $$$1$$$)
  • $$$2 \to 3$$$ (绿色,重量 $$$4$$$)
  • $$$3 \到 4$$$ (蓝色,重量 $$$4$$$)

我们有$$$s_r = s_g = s_b = 4$$$。因此,答案是$$$0$$$。