問題文の条件は単純でないパスを含めて考えても厳しくなりません。以降の解説では単純でないパスについても考慮することにします。

頂点 \(1\) から頂点 \(u\) へのパス \(p=(v_1,\ v_2,\ \dots,\ v_k)\ (v_1=1,\ v_k=u)\) に対し、\((B_1,\ B_2, \dots,\ B_i)\) が \((A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})\) の部分列となるような最大の \(i\) （存在しないならば \(0\)）を \(f(p)\) と書きます。また、頂点 \(1\) から頂点 \(u\) へのパス \(p\) に対する \(f(p)\) の最小値を \(d_u\) とします。

問題で述べられた条件については \(d_{N}=K\) かどうかで判定できるので、 \(d_u\ (1\le u \le N)\) を求めることを目標とします。

[1] \(f(p+(u'))\) についての考察

\(p\) を頂点 \(1\) から頂点 \(u\) へのパス、\(u'\) を \(u\) の隣接頂点とします。

頂点 \(1\) から頂点 \(u'\) へのパス \(p'=(v_1,\ v_2,\ \dots,\ v_k,\ u')\) に対し、 \(f(p')\) を考えます。定義に沿って考えたとき、 \(p\) と \(p'\) では \((A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})\) に対し \(A_{u'}\) が追加されただけなので、\(A_{u'}=B_{f(p)+1}\) のとき \(f(p')=f(p)+1\) 、そうでないとき \(f(p')=f(p)\) となります（部分列判定の際の貪欲法を考えるとよいでしょう）。

このことからまず頂点 \(1\) から頂点 \(u\) へのパス \(p,\ q\) であって \(f(p) < f(q)\) が成り立つとき、\(f(p+(u')) \leq f(q+(u'))\) が成り立ちます。よって \(d_{u'}\) を定める際、頂点 \(u\) を経由するパスについては \(f(p)\) の最小値、すなわち \(d_u\) のみを考えればよく、

\( d_{u'} =\min_{u} \begin{cases} d_u+1 & (A_{u'}=B_{d_u+1}) \\ d_u & (A_{u'}\neq B_{d_u+1}) \end{cases} \)

が成り立ちます。

[2] 01-BFS で求める

以上の考察から以下のようなアルゴリズムで \(d_u\) が求まることがわかります。正当性は ダイクストラ法と同じように示せます。

1. \(d_u\) について \(d_u\ (u \neq 1)\) は \(K+1\) で初期化する。 \(d_1\) については \(A_1=B_1\) のとき \(1\) で、そうでないとき \(0\) で初期化する。
2. \(d_u\) が未確定であるような \(u\) からなる集合 \(S\) を \(S=\{1,\ 2,\ \dots,\ N\}\) で初期化する。
3. \(S\) が空でない限り以下を行う。
   • \(u \in S\) のなかで \(d_u\) が最小のものは、 \(d_u\) が確定するので、\(S\) から除く。その後、\(u\) に隣接する頂点 \(u'\) について \(A_{u'}=B_{d_u+1}\) のとき \(d_{u'}\leftarrow \min(d_{u'},\ d_u+1)), \) そうでないとき \(d_{u'}\leftarrow \min(d_{u'},\ d_u))\) で更新する。

実装の際は 01-BFS と同じ要領で実装することで \(O(N+M)\) で計算できます。