# JOIG2022/2023 春合宿 B - テレポーター (Teleporter)

## 問題リンク
- https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_b

## 解説

### 方針
思いつく方針としては,次のようなものがあります.

- 具体的な最適な戦略を考える
- 全探索を高速化する(dpなど)

今回はdpを駆使して探索を行います.

### 考察
以下のようなことが分かります.

- 2人が最適な戦略をとるとする.ビ太郎が頂点 $N$ に到達できるならば,ビ太郎が同じ頂点を $2$ 回以上訪れることはない.

もしビ太郎が同じ頂点を通るならば, その時点でビ太郎は状態をループしていることになり, ビバ子の最適な戦略によりビ太郎は永遠に頂点 $N$ に到達できません.

### 解法
上の考察により,状態がビ太郎の位置のみにより決定できることが分かります.
よって,以下のようなdpが思いつきます.

- $f(i)=$ ビ太郎が頂点 $i$ にいて,この状態から2人が最適な戦略をとるとする. この状態から頂点 $N$ に到達するために必要なラウンド数.(到達できないなら $+\infty$)

遷移を考えると以下が成り立ちます:

$$ f(i) =\min_{j=1,2,\dots,A_i}\left( \max\left(f(P_{i,j}),f(Q_{i,j})\right)+1\right)$$

あとはこれを $f(i)$ の昇順に埋めていくことで求めることができます(dijkstraっぽくやる)

### 実装
- https://atcoder.jp/contests/joigsp2023/submissions/44889808

よく考えるとpriority_queueでなく,普通のququeでよいです.

- https://atcoder.jp/contests/joigsp2023/submissions/44890486