Project Selection Problem(燃やす埋める問題)とみなすこともできます。

頂点\(v\)ごとに

1. 頂点\(1\)からたどり着くことができる
2. 頂点\(1\)からたどり着くことができない
3. 壁を建てる

の\(3\)つの選択肢のうちいずれかを選びます。

選択肢1を選んだ頂点から選択肢2を選んだ頂点へ直接たどり着くことはできません(途中で選択肢3を選んだ頂点を経由する必要がある)。したがって辺\((a_i,b_i)\)について、”\(a_i\)で選択肢1を選び、\(b_i\)で選択肢2を選ぶ”または、”\(b_i\)で選択肢1を選び、\(a_i\)で選択肢2を選ぶ”ような選択には\(\infty\)のコストがかかるようにする必要があります。ただし、頂点\(1\)は選択肢1を、頂点\(N\)は選択肢\(2\)を必ず選ばなければならないことに注意してください。

3つ以上の選択肢がある場合のProject Selection Problemのグラフの作り方は以下の記事を参考にしてください。

3つ以上の選択肢がある燃やす埋める問題

できるグラフは公式解説のグラフと同じものになります。