次のような \(2N\) 頂点 \(2M + N - 2\) 辺の重み付き有向グラフ \(G'\) を構成します。

• 頂点集合は \(1, 2, \dots, N\) および \(1', 2', \dots, N'\) からなる。
• \(2 \leq i \leq N-1\) について \(i \to i'\) に容量 \(c_i\) の辺を貼る。
• \(1 \leq j \leq M\) について、\(a_i' \to b_i\) および \(b'_i \to a_i\) に容量 \(\inf\) の辺を貼る。

すると、実は次の事実が従います。

条件を満たすように壁を建てるコスト \(C\) は、始点 \(1'\) , 終点 \(N\) としたときの \(G'\) の最小カットの容量と等しい。

順を追って確認していきましょう。

観察 1

元の問題で与えられた無向グラフを \(G\) とする。\(G\) 上の \(1 - N\) 間の点素なパスは、 \(G'\) 上の \(1' - N\) 間の点素なパスと一対一対応させることができる。(「点素」とは同じ頂点を \(2\) 回以上含まないことを言う。)

\(G'\) をよく見ると、任意の \(a\) について \(a\) から伸びる辺は \(a'\) だけで、\(a'\) から伸びる辺はダッシュのつかない頂点だけです。よって \(G'\) 上の \(1' - N\) 間のパスは \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\) のような形で表せることがわかります。ここから、

• \(G\) 上の点素なパスを \(1=p_0,p_1,\dots,p_k=N\) と
• \(G'\) 上の点素なパス \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\)

を一対一対応させると、片方を定めたときにもう片方が一意に定まることから全単射が証明できると思います。

観察 2

\(S \subseteq \lbrace 2,3,\dots,N-1 \rbrace\) とすると、次の \(2\) つの命題は同値である。

1. \(S\) に含まれる数の書かれた頂点に壁を建てたとき、青木君は頂点 \(1\) から頂点 \(N\) へ向かうことができなくなる。
2. すべての \(i \in S\) について\(i\) から \(i'\) へ向かう辺を取り除いたとき \(1' \to N\) へ向かうパスは存在しなくなる。

命題 1 を言い換えると、すべての \(G\) 上の\(1 - N\) 間の点素なパス \(p_0,p_1,\dots,p_{k-1},p_k\) について、ある \(v \in S\) が存在して、\(v \in \lbrace p_1,\dots,p_{k-1}\rbrace\) である、と言い換えられます。
このとき、観察 1 で対応する \(G'\) 上のパス \(1'=p_0', p_1, p_1',\dots,p_{k-1}',p_k=N\) にも辺 \(v \to v'\) が含まれているので、\(v \to v'\) を取り除かれているとこのパスは成立しません。詳細は略しますが、このような方向性で議論を進めれば正当性が確かめられます。

以上の観察により、元の問題は \(G'\) のグラフ上の辺のうち 辺 \(v \to v'\) \((2 \leq v \leq N-1)\) のみをカットできるときの \(1' \to N\) 間の最小カット問題に帰着することがわかりました。

これは AtCoder Library を利用すれば最小カットの復元も含めて \(\mathrm{O}(N^2M)\) で計算することができるので、この問題を十分高速に解くことができます。