CF2077G RGB Walking

[Red and Blue and Green - fn and Silentroom](https://www.youtube.com/watch?v=UeN7U474cxE) 给定一个包含 $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 完成