AOJ 0244 （Hot Spring Trip : 温泉旅行）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0244
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0244
【解説】
AOJ 0212の類題。
隣接リストのキーを（町の番号,チケットの状態）の組み合わせで管理する。
チケットの状態を「未使用」、「使用中」、「使用後」の3つの状態として考えると、現在の町から次の町への辺の張り方は以下のパターンとなる。
- 現在が「未使用」の場合
⇒「未使用」または「使用中」 - 現在が「使用中」の場合
⇒「使用後」 - 現在が「使用後」の場合
⇒「使用後」
上記のグラフに対し、ダイクストラ法を用いて各ノードへのコストを求めた後、目的地のマスのノードのコストを出力する。
出力するチケットの状態については、制約として、「途中で目的地を通過しても、目的地にたどり着いたことにはなりません。」とあることから、使用中のノードの値は使用できないこと、また町の数が2の場合はチケットを使用できないことから、「未使用」または「使用後」の状態のうち、コストが小さい方を出力すればよい。
【コード】
