SRM461 Div1 Medium(500) BuildingCities

BuildingCities

ダイクストラ法。任意の街iから街jについて、iとjを結ぶ線分上にmaxDirectごとに街を建設すれば、iとjの直線距離で移動できる。街iとiに到達するまでに建設した街の数jをペアにしたをノードとする。街iと街jの直線距離がdでb個の街を建設することで到達できるならば、とにコストdの辺がある。そのまま書くと制限時間をオーバーするけど、建設する街の数が多くて距離も長いノードは生成しないことで高速化。

#include <vector>
#include <cmath>

using namespace std;

class BuildingCities
{
public:
    int findMinimumCities( int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY );
};

int BuildingCities::findMinimumCities( int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY )
{
    //  街の数
    int n = (int)cityX.size();

    //  [i][j]　街iと街jの距離の2乗
    vector<vector<int> > dist2( n, vector<int>( n ) );

    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
        dist2[i][j] = (cityX[i]-cityX[j])*(cityX[i]-cityX[j]) + (cityY[i]-cityY[j])*(cityY[i]-cityY[j]);

    //  [i][j]　街iから街jへmaxDirect以内で移動するために必要な街数
    vector<vector<int> > build( n, vector<int>( n ) );
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
        for ( int k=1; ; k++ )
            if ( dist2[i][j] <= maxDirect*k*maxDirect*k )
            {
                build[i][j] = k - 1;
                break;
            }

    //  建設する街数の上界+1
    int m = build[0][n-1] + 1;

    //  [i][j]　街iにj個の街を建設して到達する最短距離
    vector<vector<double > > node( n, vector<double>( m, 99999999 ) );

    //  [i][j]　街iにj個の街を建設して到達するノードが、0:未到達 1:未確定 2:確定
    vector<vector<int> > flag( n, vector<int>( m, 0 ) );

    node[0][0] = 0;
    flag[0][0] = 1;

    while ( true )
    {
        //  未確定で距離が最短のノードを探す
        //  未確定ノードが無ければ終了
        int mc = -1;
        int mb = -1;

        for ( int i=0; i<n; i++ )
        for ( int j=0; j<m; j++ )
            if ( flag[i][j] == 1  &&
                 ( mc == -1  ||  node[i][j] < node[mc][mb] ) )
                mc = i,  mb = j;

        if ( mc == -1 )
            break;

        //  このノードを確定し、コストを更新
        flag[mc][mb] = 2;

        for ( int i=0; i<n; i++ )
        if ( i != mc )
        {
            int     b = mb + build[mc][i];                          //  建設街数
            double  d = node[mc][mb] + sqrt((double)dist2[mc][i]);  //  距離

            if ( b >= m )
                continue;

            //  建設街数が少なく、距離が短いノードがあれば追加しない
            bool f = true;
            for ( int j=0; j<b; j++ )
                if ( node[i][j] <= d )
                    f = false;

            if ( f  &&
                 d < node[i][b]  &&
                 d <= maxTravel )
                node[i][b] = d,
                flag[i][b] = 1;
        }
    }

    //  建設した街数の最小値を返す
    for ( int i=0; i<m; i++ )
        if ( flag[n-1][i] == 2 )
            return i;

    return -1;
}