https://atcoder.jp/contests/abc132/submissions/11351529
modグラフとでも暗記すると良いかもしれない。
- グラフの頂点数を3倍に増やす⇔結果を格納する配列の次元を増やすことで実現
- 上記に合わせてqueueもpair<ll, ll>にすると実装が楽
- 結果を格納する配列の初期値をLLONG_MAX(INF)、スタート地点を0にする
- BFSしていきLLONG_MAXつまり未更新だったら更新
結果を格納するres配列をres[i][j]:=頂点iでmod3の値がjとなる最短経路とする。mod上をBFSしてans[T][0]が答えになるが、設問では3回の移動を1回とカウントするため最後に3で割った答えを出力する。
