ABC132 E Hopscotch Addict
https://atcoder.jp/contests/abc132/submissions/7044671
所感
拡張ダイクストラ、ノードを増やすんだけど、実際に実装するときは距離を格納する配列の次元を増やすみたいな実装になるんだなあ
問題概要
有向グラフの上で移動することを考える。頂点Sから頂点Tに移動するとき、移動距離が3の倍数となる経路は存在するか、するならばその経路の長さを3で割ったものを出力せよ。
取った方針
BFSで頑張ろうとするも死亡
正しい方針(解説の方針)
一般に拡張ダイクストラとか呼ばれている方法をする。(今回は辺のコストが1なのでBFSでよい)
それぞれのノードについて、そこに至る経路長 mod 3 が0, 1, 2 の場合について場合分けする。
元のグラフについて、辺(a, b) が存在するとき、辺(a0, b1)、(a1, b2)、(a2, b0)を張ったグラフを考えて、そのうえでS0からT0に到達するパスがあればよい。
上記のグラフに対してBFSなりダイクストラなりを行うとOK
このとき、実装は実際にグラフの頂点を増やすのではなく、最短経路を保持する配列distの次元を増やし、キューに次展開するノードだけでなく状態も合わせて入れておくと(例: pair (2, 1) がノード2、経路長mod 3 が1であることを表し、dist[2][1] はノード2に経路長mod 3 が1で来る場合の最短経路を表す)実装が楽。
参考:
得られた知見
・探索 + 状態を持つ -> 拡張ダイクストラ / BFS
・拡張ダイクストラは最短経路を持つ配列distの次元を増やすと実装が楽
解くのに必要な要素
・状態の数だけノードを増やしたいと思う心
周辺調査によって得られた知見
特になし
