SRM475 Div2 Hard(1000) RabbitJumping

RabbitJumping

小さいジャンプでは位置の偶奇は変わらず、穴を飛び越えることはできない。穴で分けられた各区間の偶数と奇数の位置をそれぞれノードとして、ある区間の偶数（奇数）からある区間の奇数（偶数）の位置に大きいジャンプができる場合に、コスト１のエッジを張ると、グラフの最短経路問題になる。

#include <vector>

using namespace std;

class RabbitJumping
{
public:
    int getMinimum( vector <int> holes, int largeJump );
};

int RabbitJumping::getMinimum( vector <int> holes, int largeJump )
{
    int n = (int)holes.size()/2;

    if ( largeJump % 2 == 0 )
        return -1;

    //  この区間に到達する最小ジャンプ数（0:偶数、1:奇数）
    vector<int> dist[2];
    dist[0] = dist[1] = vector<int>( n+1, -1 );
    dist[0][0] = 0;

    for ( int d=0; d<2*(n+1); d++ )
    {
        for ( int b=0; b<2; b++ )
        for ( int f=0; f<=n; f++ )
        if ( dist[b][f] == d )
        {
            for ( int t=0; t<=n; t++ )
            {
                //  移動元・異動先区間の最左・最右の位置
                long long fl = f>0 ? holes[f*2-1]+1 : -2000000000ll;
                long long fr = f<n ? holes[f*2]-1   :  2000000000ll;
                long long tl = t>0 ? holes[t*2-1]+1 : -2000000000ll;
                long long tr = t<n ? holes[t*2]-1   :  2000000000ll;

                if ( fl%2 != b   )  fl++;
                if ( fr%2 != b   )  fr--;
                if ( tl%2 != 1-b )  tl++;
                if ( tr%2 != 1-b )  tr--;

                if ( tr - tl >= 0  &&
                     ( f <= t && tl-fr <= largeJump && largeJump <= tr-fl ||
                       f >= t && fl-tr <= largeJump && largeJump <= fr-tl ) &&
                     dist[1-b][t] == -1 )
                    dist[1-b][t] = d+1;
            }
        }
    }

    return dist[1][n];
}