ABC143-E Travel by Car
概要
N(N <= 300)個の町をM(M <= N(N-1)/2)本の道がつないでる。それぞれの道には距離D(D <= 10^9)が設定されてる。あなたの車は最初燃料L( L <= 10^9)まで積んでおり、距離1走るごとに燃料1を消費する。町で燃料の補給ができるが、道の途中で燃料を切らしてはいけない。
Q( Q <= N(N-1)/2)個のqueryがあり、それぞれ始点sから終点tまで行くのに必要な燃料補給数の最小値を答えよ。
ACするまで
1. 制約がワーシャルフロイドを呼んでる！しかし、例えば燃料が10まで入り、s -> tが距離39の時、補給回数が必ず 39/10 - 1 = 2.9 -> 2回とはならない。
2. 経路復元を考えたけど、になる。険しい
3. ダイクストラも一瞬考えたらいずれにしろ厳しい。
4. 言い換えを行う。ある点xから満タンの状態で補給なしで行ける頂点をコスト1、それ以外をコスト∞とする。それ以外の頂点は確実に何回かはわからないため、確実に1回で行ける頂点だけをピックアップした。
5. ここで、確実に1回の満タンで行ける頂点間だけに辺が張られる。この辺をうまくたどっていけば、最短の回数とわかる！
考察
この問題の構造としては、
1回の満タンで行ける距離は定まるが、それ以上は定まらない
というのが挙げられる。
この問題のタイプの問題は、僕が見た限り多項式時間でとけなさそう（要参考）
しかし、特殊な縛りを付けた問題ならば可能といえる。
この問題に対してとる手段は、
一つ後でつながるもの(つまり、確実に確かといえるもの)だけを選び、それらを辺としてグラフで解く！（小さいサイズに限る、例外あり）
例外としては、一本道の場合で、その場合はダブリングの手法が通用する。(高橋君とホテル)
この問題では、その手段をとることで愚直にワーシャルフロイドしても計算量的には通る。
一言
盲点だった。会心の敗北。
