JOI 13本選 C 現代的な屋敷(難易度8)
グラフに帰着する. 最短時間なので, スイッチのある部屋のみを頂点として考えたダイクストラ法をする. 同じ行・列にあるスイッチ同士で辺を張ると辺数が
$ O(N^2)
となって間に合わないが, 行・列で隣り合う頂点のみに辺を張ることで辺数が
$ O(N)
となりダイクストラ法をしても
$ O(N log N)
となって間に合う.
実装が重い.
実装例:
https://atcoder.jp/contests/joi2013ho/submissions/19429111