ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 1138 - Traveling by Stagecoach

問題
提出コード

解法

単一始点最短路問題なので、なんとなくダイクストラ法が使いたいなぁ、という気持ちになりました。
その後、馬車券の枚数を見ると、制約が8ととても少なく、都市の数自体も30以下とかなりすくないことから、馬車券を使ったかどうかbitで持たせておきつつダイクストラ法をしても時間が間に合いそう、ということがわかります。
配列を用意し、dp[i][j] = 馬車券を使った状態がjでのときに都市iにいるような行き方の最短距離、とします。
jはビットで使ったかどうかを判定するものになります。
こうすることで、dp[b][j]の最小値が答えになります。 あとはいつもと同様にダイクストラ法をすれば答えが求まります。
切符を使い切っても都市bにたどり着くことができなければ、Impossibleを出力することを忘れないようにしましょう。