P16024 [ICPC 2021 NAC] TraveLog

久别重逢后，Alice 和 Bob 终于再次相聚。他们生活在一个有 $n$ 座城市的国家中，这些城市被别出心裁地命名为城市 $1$ 到城市 $n$。Bob 从他的家乡城市 $1$ 开车前往 Alice 的家乡城市 $n$。 当 Alice 问 Bob 走的是哪条路时，Bob 惊讶地发现自己完全不记得了。Bob 是个高效的人，他一路上没有停歇，并且知道没有比他所走的路更快的一条路。他还拥有一个全新的国家探险公司（NAC）行车日志！每当 Bob 经过一座城市时，行车日志会记录下他从离开城市 $1$ 到抵达当前城市之间所经过的时间。 :::align{center}  ::: 在上图所示的道路布局中，Bob 从城市 $1$ 到城市 $n$ 可能存在两条最快的路径：$1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ 或 $1 \rightarrow 4 \rightarrow 5$。两条路径的总时间均为 $9$ 个单位时间。第一条路径对应的行车日志为 $0, 3, 7, 9$，第二条路径对应的行车日志为 $0, 5, 9$。 不幸的是，Bob 的行车日志存储器发生了损坏。Bob 认为部分时间记录已经丢失，而剩下的记录则被随机打乱了顺序。给定行车日志中残留的记录，你能否重建 Bob 的行驶路径？

输入的第一行包含三个整数 $n$（$2 \le n \le 2 \cdot 10^5$）、$m$（$1 \le m \le 3 \cdot 10^5$）和 $d$（$1 \le d \le n$），其中 $n$ 是国家的城市数量，$m$ 是这些城市之间的单向道路数量，$d$ 是 Bob 损坏的行车日志中剩余的时间记录条数。城市编号为 $1$ 到 $n$。Bob 住在城市 $1$，Alice 住在城市 $n$。 接下来的 $m$ 行，每行包含三个整数 $u$、$v$（$1 \le u, v \le n, u \ne v$）和 $h$（$1 \le h \le 10^6$）。每行描述一条从城市 $u$ 到城市 $v$ 的单向道路，通行需要 $h$ 个单位时间。保证至少存在一条从城市 $1$ 到城市 $n$ 的路径。任意一对城市之间可能有多条道路。 接下来的 $d$ 行，每行包含一个整数 $t$（$0 \le t \le 10^{18}$）。这些是 Bob 的行车日志中残留的记录。每行记录的是 Bob 从城市 $1$ 出发到他所经过的另一个城市所花费的时间。这些值保证互不相同。

输出格式取决于与 Bob 的行车日志记录一致的路径条数。 - 如果没有一致的路径，输出 $0$。 - 如果存在多条一致的路径，输出 $1$。 - 否则，在第一行输出 Bob 路径上的城市个数。在接下来的若干行中，按访问顺序输出 Bob 途经的城市，每行一个。

翻译由 DeepSeek V3.2 完成