第16回日本情報オリンピック　予選６

2016年12月11日
情報オリンピック日本委員会

解説

この問題は，グラフ理論の分野の問題である．すなわち，部屋と廊下の構造をグラフとみなしたとき，頂点 1 から頂点 N まで条件を満たしながら移動するときの最短距離を問う問題である．

部屋の温度に関する条件がない場合，この問題はよく知られたアルゴリズムであるダイクストラ法を用いて解くことができる．ここでは，ダイクストラ法を応用してこの問題に適用できるようにすることを考えよう．

ダイクストラ法では，経路を探索する際，始点からの経路長 d とその時点での頂点の番号 v の組を状態として持つ．しかし，この問題では部屋の温度に関する条件があるため，それらの情報だけでは次に使用できる辺集合が定まらない．次に使用できる辺集合は，d, v に加えて以下の情報があれば定まる．

• 経路上で最後に入った快適でない部屋は暑すぎる部屋であったか，寒すぎる部屋であったかを示すビット b
• 経路上の最後に入った快適でない部屋と，現在の頂点との (経路に沿った) 距離 d'

このうち後者は，値が X 以上である場合は X であるとみなしても次に使用できる辺集合に変化はない．すなわち，d, v, b, min{X, d'} という 4 個の値から次に使用できる辺集合が定まることになる．

以上より，状態として 4 個の値の組 (d, v, b, min{X, d'}) を持ちながらダイクストラ法を行えば条件を満たす最短経路が求まることがわかる．計算量は，2N(X + 1) 頂点 2M(X + 1) 辺のグラフで普通のダイクストラ法を行うのと同等であり，十分高速である．