AOJ 0224 （Bicycle Diet : 自転車でダイエット）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0224
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0224
【解説】
今まで訪れたケーキ屋を状態として保持するためにノードを多重化して扱い、消費カロリーをコストとしてダイクストラ法で最短距離を求める。
始めに、仮にケーキ屋が一つも無かったとすると、無向グラフの最短距離なので、通常のダイクストラ法で問題なく実施可能である。今回の設問ではケーキ屋があることで以下の条件が追加となる。
- ケーキ屋に到達した場合、指定の値をコストから減じる。
- 一度到達したケーキ屋を再度訪れることはできない。
そのため、通常のダイクストラ法では一度コストが確定したノードについては再度コストが更新されることはないが、１．の条件により再度訪問する場合があり得る。（例として、L1⇒C1⇒L1の経路があった場合、道路のコストとケーキ屋で減少されるコストの関係性によっては初回のL1よりもケーキ屋訪問後のコストの方が低くなる。）
そのため、ケーキ屋の数は高々６軒なので、ケーキ屋を訪れた状態（2^6）ごとにノードを分けて管理し、ケーキ屋を通過するたびに通過した状態のノードにたどり着くように候補となる辺を結んであげればよい。その際、１．の条件を実装するため、ケーキ屋を訪問する際にはコストを減少させ、２．の条件を実装するため、すでに枝候補に追加するケーキ屋が訪問済みの場合は枝刈りする。
なお、２．の条件によりケーキ屋を含む閉路は存在し得ないため、経路が決定できないことは考慮しなくてよい。（仮に再度訪れることが認められると、閉路内の道路のコスト＜ケーキ屋で減少できるコストとなる場合に閉路をぐるぐるすることで、いくらでもコストを減じられてしまうことになる）
最後に、ゴールの各状態ノードについて、最もコストを低いものを出力すれば、これが答えとなる。
【コード】
