https://atcoder.jp/contests/zone2021/submissions/23283470
- 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能
- コストを増やしたい→階層化して辺を追加すれば再現可能
上下左右1マス移動しかないなら単純にダイクストラ法をするだけで処理できる。しかし、今回は任意の頂点から最大R本の辺が張られているため、何も工夫せずにダイクストラ法をするとで間に合わない（じつは定数倍高速化すれば間に合うらしいが）。そこで
を
に落とす方法を考える。
ここで仮に (x, y) から (x-i, y) への移動がコスト i+1 でなくコスト i だった場合、各頂点からR本の辺を貼る必要はなく (x, y) から (x-1, y) にコスト1の辺を1本ずつ貼るだけで同じ移動を再現できる（唐突）。問題はコストが i でなく i+1 であることだが、これは図のように階層化することで解決できる。
例えば (5, 10) から (2, 10) へコスト4で移動したいなら、1階の (5, 10) から2階の (5, 10) へコスト1で移動し、2階の (5, 10) から2階の (2, 10) へコスト1の辺を1本ずつ辿って合計コスト3で移動し、2階の (2, 10) から1階の (2, 10) へコスト0で移動すれば良い。したがって、頂点を2倍に増やして階層化し上記方法で辺を貼ると で処理できるようになる。
感想: 階層化によるコストの調整は典型テクとして覚えておきたいと思った…
