GitHub 源文件 Markdown English

转动的字节¶

预估时间限制：4 秒。内存限制：4096 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

你齿轮上转动的字节，是我此生不变的信仰。

巴贝奇终究没能完成他的分析机。后来，采用电磁继电器的电动计算机，以及采用电子管、晶体管和半导体器件的电子计算机相继出现，以另一种方式实现了他的毕生夙愿。

形式化问题描述¶

有一个 \(n\) 个结点、\(m\) 条边的有向图，结点编号为 \(1,\ldots,n\) .每个结点和每条边都有一个非空二进制字符串标签。结点一是终点，另给出 \(k\) 个不同的可选起点，均不为一。允许重边和自环。

路径字符串依次连接起点标签、第一条边标签、下一个结点标签，直到终点标签。按照以下优先级选择路径：

从某个可选起点到结点一，路径字符串长度最小。
在长度最小的路径中，路径字符串的字典序最小，字符 0 小于 1 .
在前两项均相同的路径中，将经过的结点编号从终点到起点排列，使该编号序列字典序最小。每个编号作为一个整数比较，不按它的十进制字符比较。

序列的字典序比较在第一个不同位置决定大小；若一个是另一个的真前缀，则较短者较小。输出所选路径的正向字符串及正向结点序列。若不同重边给出完全相同的两项输出，不必区分这些边。保证至少存在一条可行路径。

输入格式¶

第一行三个整数 \(n,m,k\) .第二行 \(n\) 个字符串，依次为结点标签。第三行 \(k\) 个起点编号。接下来 \(m\) 行，每行两个整数 \(u,v\) 和一个字符串 \(s\) ，表示从 \(u\) 到 \(v\) 的有向边及其标签。

输出格式¶

第一行输出正向路径字符串。第二行从起点到终点输出经过的结点编号，用空格分隔。

样例¶

样例 1¶

输入¶

12 15 2
00 1 0 1 1 1 0 0 0 1 101 101
11 12
3 1 00000
2 1 1111
4 3 0
4 2 1
6 4 0
7 4 1
5 6 1
5 7 1
9 5 1
10 5 1
8 9 1
8 10 1
12 8 1
11 8 1
4 2 1

输出¶

101101011101111111100
11 8 9 5 7 4 2 1

样例 2¶

输入¶

输出¶

00000
4 2 1

样例 3¶

输入¶

输出¶

0101
3 1

样例解释¶

样例一的完整有向图见下图；圆内为“编号 / 点标签”，边旁为边标签，两条 \(4\to2\) 的平行边都画出。高亮路径为输出路径。样例二两条路线都产生五个零，但反向编号序列 \((1,2,4)\) 小于 \((1,3,4)\) .样例三两条直达路线字符数相同，从结点三出发的字符串更小，自环会增加长度。

样例一的完整网络和所选路径

数据范围与保证¶

\(2\le n\le2\times10^6\) , \(1\le m\le3\times10^6\) , \(1\le k\le n-1\) . 所有点、边标签长度均为一到五，只含 0 和 1 .所有编号合法，且至少一个可选起点可达终点。

分值比例	额外条件
20%	\(n,m\le10\)
30%	\(n\le1000\) , \(m\le2000\)
20%	\(n\le300000\) , \(m\le500000\)
30%	无额外条件