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

2
1 0
2 2
1 1 a
2 1 b

输出 #1

0
0 -1

输入输出样例 #2

输入 #2

2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y

输出 #2

0 1 1 5 2 3 4
0 1 2 -1

说明/提示

样例 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 完成