CF2077G.RGB Walking

Red and Blue and Green - fn and 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$ 为红色（red）、绿色（green）或蓝色（blue）。保证图中至少存在一条每种颜色的边。

对于一条允许重复顶点和边的路径，设 $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)$ 的最小值。

第一个测试用例中，最优路径为 $1 \to 2 \to 3 \to 4$。使用的边依次为：

• $1 \to 2$（红色，权重 $2$）
• $2 \to 3$（绿色，权重 $3$）
• $3 \to 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 \to 2$（红色，权重 $1$）
• $2 \to 1$（红色，权重 $1$）
• $1 \to 2$（红色，权重 $1$）
• $2 \to 3$（绿色，权重 $4$）
• $3 \to 4$（蓝色，权重 $4$）

此时 $s_r = s_g = s_b = 4$，因此答案为 $0$。

翻译由 DeepSeek R1 完成