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までの最短経路を探索する