切符分割

原案　松岡

問題概要

・駅の間の距離と、運賃表が与えられます。

・切符を２枚まで購入することで達成できる、最も安い交通費を求めてください。

部分点　分割なし　想定解法

・部分点１は切符の分割がありません。

・N、Mの制約も小さいので、お好きな方法で、S-Gの最短距離を求めてください。

（ワーシャルフロイド、ベルマンフォード、ダイクストラ）

部分点　N,Mの制約が小さい

・１．ワーシャルフロイドなどで、全点間の最短距離を求める

・２．d(i,j)をi番目の駅からj番目の駅までの距離としたとき、すべてのiについて、

ans = min(cost(d(s,i))+cost(d(i,g)))

・2に気が付ければこの部分点までは獲得できるはず

満点解法

・ワーシャルフロイドでは間に合いません。

・負の辺は存在しないのでダイクストラを使いたい。

・ほしい距離は、始点からの距離と、終点からの距離の二つだけ。

満点解法

・ダイクストラを　始点→途中→終点とやると、すべての駅についてダイクストラをしなければならないが、　始点→途中　と　途中←終点とすると、始点と終点の二つから探索すればよい。

・計算は二倍にしかならないので、計算量としては無視できる

満点解法について

・幅優先探索でも似たようなことができる場面があります。

（ダイクストラと幅優先はコードも似た感じで書けますしね）

元ネタ

・JRの運賃

・久留米から香椎まで行く場合、天拝山で一度� 降りると10円安くなります(2014/03/28現在)

・テストケースにも同じものを含めました