7K12 blog

猫でも分かるアルゴリズム解説

ABC132 E - Hopscotch Addict

f:id:tkr987:20200511151857p:plain

https://atcoder.jp/contests/abc132/submissions/11351529

modグラフとでも暗記すると良いかもしれない。

  • グラフの頂点数を3倍に増やす⇔結果を格納する配列の次元を増やすことで実現
  • 上記に合わせてqueueもpair<ll, ll>にすると実装が楽
  • 結果を格納する配列の初期値をLLONG_MAX(INF)、スタート地点を0にする
  • BFSしていきLLONG_MAXつまり未更新だったら更新

f:id:tkr987:20200511152459p:plain

結果を格納するres配列をres[i][j]:=頂点iでmod3の値がjとなる最短経路とする。mod上をBFSしてans[T][0]が答えになるが、設問では3回の移動を1回とカウントするため最後に3で割った答えを出力する。