P15261 [USACO26JAN2] Lexicographically Smallest Path G

Bessie 拿到一个无向图，该图包含 $N$（$1\le N\le 2 \cdot 10^5$）个编号为 $1\dots N$ 的顶点和 $M$ 条边（$N - 1\le M\le 2 \cdot 10^5$）。每条边由两个整数 $u, v$（$1\le u, v \le N$）和一个小写英语字母 $c$（范围 a..z）描述，分别表示结点 $u$ 和 $v$ 之间的一条无向边以及该边上的值。给定的图保证是连通的。图中可能存在重边或自环。 定义 $f(a, b)$ 为从结点 $a$ 开始到结点 $b$ 结束的所有路径中，边值连接形成的字符串中字典序最小的那个。一条路径可以多次包含同一条边（即允许环）。 对于每个 $i$（$1\le i \le N$），帮助 Bessie 确定 $f(1, i)$ 的长度。如果该长度有限，则输出该长度；否则输出 $-1$。

第一行包含 $T$（$1\le T\le 10$），表示独立测试用例的数量。每个测试用例的格式如下： - 第一行包含 $N$ 和 $M$。 - 接下来的 $M$ 行，每行包含两个整数和一个小写英语字母。 保证所有测试用例的 $N$ 之和以及 $M$ 之和均不超过 $4\cdot 10^5$。

对于每个测试用例，在新的一行输出 $N$ 个由空格分隔的整数。

#### 样例 1 解释 对于第一个测试用例，结点 1 可以通过空路径到达，因此答案为 0。在第二个测试用例中，结点 2 不存在字典序最小的路径，因为农夫约翰可以在移动到结点 2 之前重复 'a' 自环任意多次，从而产生任意长但仍为字典序最小的字符串。因此，结点 2 的答案为 -1。 #### 样例 2 解释 对于第一个测试用例，结点 1 的距离为 0。结点 2 和结点 3 与结点 1 相邻，距离为 1。对于结点 4、5、6 和 7，可以证明字典序最短的路径不经过结点 2 和结点 4 之间的边。 对于第二个测试用例，结点 4 同样没有字典序最小的路径，因为字符串可以在保持字典序最小的同时无限延长。因此，其答案为 -1。 ### 评分 - 输入 3-4：每条边上的字符均为 a。 - 输入 5-8：每条边上的字符为 a 或 b。 - 输入 9-14：$N,M\le 5000$ - 输入 15-22：无额外约束。 翻译由 DeepSeek 完成