AOJ2021 Princess in Danger
引き続き最短経路問題の復習をしている。いよいよ典型問題と言うのは無理があるかもしれないが、各頂点に状態があるダイクストラ法の問題。
この問題はそれぞれの冷凍施設で何分冷凍するかというのが問題になるが、ゴールで残り時間が0秒になる場合の最適な冷凍時間を、逆順に辿りながら計算することで解決した。手順としては、ゴール時点で残り時間を0秒として、経過した時間だけ秒数を足していく。冷凍施設に到達した時点で残り時間を0秒に戻す（それぞれの冷凍施設に残り時間0秒で到着する場合を考える）。
しかし、実際にはゴールで残り時間が0秒にならない場合がある（ほとんどの場合はならない）ので、スタート地点に到着した段階での残り時間M'とM（出発時点での冷凍時間）の差を使って無駄な時間を除けば良い。例外を無視すれば、（M-M'）分だけどこかで無駄に冷凍した時間が計算されているので、逆順に辿りながら計算した最短時間から（M-M'）を引けば良い。
解法は良いのだが、やはり実装にバグを埋め込んでしまった。ダイクストラ法で個人的にやってしまうのがグラフの初期化ミスで、なんとなく癖でwhile文の外で初期化してしまう。AtCoderとかだとwhile文を使わないのでミスに気づかないのだが、AOJでは複数の入力を受ける必要があるので2個目以降が完全に崩壊してしまう。初期化ミスだけならすぐに気づくが、他のバグと合わさっていると意外と気がつかないので注意したい。
結局この問題もデバッグに時間がかかって1時間以上かかった。解法が思いついたらすぐに書き始めてしまうので、もう少し実際のコードを先に考えてから書き始めないといけない。
