AOJ 0212 （Highway Express Bus : 高速バス）
【問題】
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0212?year=2009
【解説】
三次元のダイクストラ法。隣接リストのキーを（町の番号,残りチケット数）の組み合わせで管理する。
各レイヤーを残りチケット枚数の数とし、一階層下のレイヤーに向かう、コスト÷2の有向辺を張ることで、割引チケットを使用した場合の経路を作成することができる。
あとは、始点（始点の町の番号,初期残りチケット枚数）からダイクストラ法で各町までの最短距離を求め、終点（終点の町の番号,0)～（終点の町の番号,初期残りチケット枚数）への最短コストを求めればOK。
最初、最短経路の本数（辺数）よりもチケットの残り枚数が多い場合を考慮していなかったためにハマった。終点（終点の町の番号,0)をOutputしていたが、先述の場合、残り枚数が0の場合が必ずしも最短コストとならないため注意。（チケットを使い切るために無駄な経路を通るため。）
gist349073f60c88b2256f6d30fe2cef5e28
