SRM551 Div1 450

とぷこだ 過去問

問題

毎晩、毛の色を変えられるオオカミがいる。
色はN色あって、便宜上0〜N-1の番号で扱う。


colorMapという2次元配列が与えられる。
もし色iから色jに変えることができればY、そうでなければNが書かれている。
色は、変化させられる最小の番号の色に変わる。
変化させる色が無い場合は、その色のままになる。


最初に色0のオオカミがいて、これを色N-1にしたい。
ここで、colorMapのYの部分をいくつかNに変化させ、これを実現したい。
そのような最小の変化の回数を返す。
色N-1にすることが不可能な場合は-1を返す。

考え方

colormap[i][j]==Yで色をiからjにするためには、0〜j-1までのYをすべてNにしないといけない。
なので、colormapのすべてのYについて、各iについてYの部分を0,1,2,...とNにしないといけない回数(コスト)を持たせた隣接行列を作る。

あとは、頂点0から頂点N-1までの最短経路を求めれば、YをNに直す最小回数が求められ、経路がなければ-1を返せばよい。

最短経路はNが50程度なので、ワーシャルフロイドで十分。