P13856 [CERC 2023] Labelled Paths

给定一个有向无环图，其中有 $n$ 个顶点和 $m$ 条边。每条边都有一个标记（由小写字母组成的字符串；可能为空字符串）。我们将“路径的标记”定义为这条路径上各边标记按路径顺序拼接而成的字符串。若从起点顶点 $s$ 到目标顶点 $t$ 存在多条路径，则其中**最小的路径**指的是其标记在所有路径的标记中按字典序最小的那条。请你编写一个程序，对于给定的起点 $s$，输出从 $s$ 到每个顶点 $t$ 的最小路径。

第一行包含四个整数，分别是 $n$（顶点数）、$m$（边数）、$d$（字符串 $A$ 的长度，见下文）、$s$（起点的编号）。顶点编号为 $1$ 到 $n$。 第二行给出一个字符串 $A$，长度正好为 $d$，所有字符均为小写英文字母。图中所有边的标记都是字符串 $A$ 的子串。 接下来 $m$ 行描述各条边。第 $i$ 行描述第 $i$ 条边，包含四个整数：$u_i$（该边的起点）、$v_i$（该边的终点）、$p_i$ 和 $\ell_i$。其中最后两个数表示该边的标记是字符串 $A$ 的一个子串：它从 $A$ 的第 $p_i$ 个字符开始，长度为 $\ell_i$。这里我们认为 $A$ 的字符编号从 $1$ 到 $d$。

输出 $n$ 行，第 $t$ 行（$t = 1, \dots, n$）描述从 $s$ 到 $t$ 的最小路径。 - 如果从 $s$ 到 $t$ 不存在路径，则这一行只输出整数 $0$。 - 否则，先输出路径上的顶点数（包含 $s$ 与 $t$），随后输出该路径上所有顶点的编号，按路径顺序排列，彼此间以空格分隔。 如果存在多条合法解，输出任意一条均可。

### 注释 在这个样例中，边 $3 \rightarrow 1$ 的标记是 "ab"；边 $1 \rightarrow 4$ 的标记是 "a"；因此从 $3$ 到 $4$ 的最小路径是 $3 \rightarrow 1 \rightarrow 4$，其标记为 "aba"。 ### 输入限制 - $1 \leq s \leq n \leq 600$ - $1 \leq m \leq 2000$ - $1 \leq d \leq 10^6$ - $1 \leq u_i \leq n$，$1 \leq v_i \leq n$，且 $u_i \neq v_i$（对所有 $i = 1, \dots, m$ 成立） - $1 \leq p_i$，$0 \leq \ell_i$，并且 $p_i + \ell_i - 1 \leq d$（对所有 $i = 1, \dots, m$ 成立） - 图是无环的，且不存在平行边（即若 $i \neq j$，则有 $u_i \neq u_j$ 或 $v_i \neq v_j$）。 --- 翻译由 ChatGPT-5 完成