题解

思路

沿一条从顶点 $1$ 出发的路径依次读取顶点权值，并用贪心法匹配 $B$：设已经匹配了前 $j$ 项，走到权值等于 $B_{j+1}$ 的顶点时令 $j$ 加一，否则保持不变。

做法

对顶点 $u$ 定义 $d_u$ 为所有从 $1$ 到 $u$ 的路径中这一匹配长度的最小值；把简单路径改为允许重复顶点的路径不会改变题目的真假。若从 $u$ 走到相邻顶点 $v$，新值只可能是 $d_u$ 或 $d_u+1$，并且转移关于 $d_u$ 单调，因此只保留每个顶点的最小值就足够。

把“不匹配下一项”的转移视为权值 $0$，把“恰好匹配下一项”的转移视为权值 $1$，即可从顶点 $1$ 开始用双端队列进行 0-1 BFS；当距离改善时，权值为 $0$ 的转移压入队首，权值为 $1$ 的转移压入队尾。最终当且仅当 $d_N=K$ 时，所有从 $1$ 到 $N$ 的路径都包含 $B$ 作为子序列。

复杂度

时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。