AtCoder Regular Contest 1 B. リモコン
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の22日目のエントリです.
ARCのB問題埋め.
問題概要
- エアコンの設定温度をA度からB度にしたい
- エアコンは1度,5度,10度刻みで温度を変えることができる
- 何回の操作が必要か
解法
- ある温度iからはi-10, i-5, i-1, i+1, i+5, i+10に1回の操作で遷移できる
- 温度をノードとして,iからi-10, i-5, i-1, i+1, i+5, i+10に対するコスト1のエッジを貼る
- 幅優先探索で温度AからBまでの最短経路を探索する