WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM579 Div1 Medium "TravellingPurchasingMan"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11050

あなたは地元の店で、何店舗でショッピングができるか気になっている。。店は0番からN-1番までN店ある。0番からM-1番までの店に、あなたは興味があり、他の店は興味が無い。いくつかの店同士は道で繋がっている。

あなたにはM個の文字列、String interestingStores が与えられ、興味のある店の説明をしている。 i 番目の要素は i 番目の店に対応しており、"OPEN CLOSE DURATION"という形式になっており、OPENは店が開店する時間、CLOSEは閉店する時間、DURATIONはその店でショッピングをしたい最低限の時間となっている。あなたは店にOPEN~CLOSEの間の任意の時間Tに訪れる事ができる。つまり、あなたは時間T(もしくはそれより早くてもよいが)に店に到着する必要がある。ショッピングはT + DURATIONに終わり、その間はずっとその店にいなくてはならない。ショッピングが終わる時間が、その店のCLOSEを過ぎてもよい事に留意せよ。あなたは同じ店でショッピングを複数回行う事はできない。

道の情報は、String roads によって与えられる。roadsの各要素は1つの双方向の道を表し、その形式は"A B LENGTH"となっている。これは、番号A、Bの店が長さLENGTHの道によって繋がっていることを意味し、LENGTHはAからB(またはBからA)へ行くのにその時間だけかかることを表している。

あなたのスタートはN-1番目の店に時間0でいる。興味のある店でショッピングすることができる店の数の最大を返せ。

制約

1 <= N <= 50
1 <= M <= min( 16, N )
1 <= 道の数 <= 50
1 <= OPEN, CLOSE, DURATION, LENGTH <= 604800


考えた事

む、時間は604800、そして店の数が50
604800 * 50 = 3000マソ・・・
これでDPするに違いない。

・・・できない

お、Mは16か、これはBitDPのかほり・・・
dp[ ショッピングした店(Bit) ][ 最後に訪れた店 ] = 最小の時間でいけそうだけど・・・
いかんせん興味のある店とない店が混在している。

ワーシャルたんで最小距離だして、興味ある店だけでDPってればいいよね


ソースコード

const int INF = (int)1e9;

int M, R;
int G[55][55];
int S[20], T[20], D[20];

int dp[1 << 16][20];

class TravellingPurchasingMan {
public:

    int countBit( int bit ){
        int res = 0;
        for( int i = 0; i < M; i++ ){
            int mask = 1 << i;
            if( (bit & mask) != 0 ) res++;
        }
        return res;
    }

    int maxStores(int N, vector <string> interestingStores, vector <string> roads){

        M = interestingStores.size();
        R = roads.size();

        // S T D初期化
        for( int i = 0; i < M; i++ ){
            sscanf( interestingStores[i].c_str(), "%d %d %d", &S[i], &T[i], &D[i] );
        }            

        // G初期化
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < N; j++ ){
                G[i][j] = (i == j ? 0 : INF);
            }
        }
        for( int i = 0; i < R; i++ ){
            int u, v, l;
            sscanf( roads[i].c_str(), "%d %d %d", &u, &v, &l );
            G[u][v] = G[v][u] = l;
        }

        // ワーシャル-フロイド
        for( int k = 0; k < N; k++ ){
            for( int i = 0; i < N; i++ ){
                for( int j = 0; j < N; j++ ){
                    G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
                }
            }
        }

        // dp初期化
        for( int i = 0; i < 1 << M; i++ ){
            for( int j = 0; j < N; j++ ){
                dp[i][j] = INF;
            }
        }
        for( int i = 0; i < M; i++ ){
            dp[0][i] = G[i][N-1];
        }

        // dp更新
        int res = 0;
        for( int vis = 0; vis < 1 << M; vis++ ){
            for( int cur = 0; cur < M; cur++ ){
                if( dp[vis][cur] == INF ) continue;

                res = max( res, countBit( vis ) );

                for( int to = 0; to < M; to++ ){

                    // 行けない
                    if( G[cur][to] >= INF ) continue;

                    int mask = 1 << to;
                    // 既に買い物した
                    if( (vis & mask) != 0 ) continue;

                    // 行ってオープンしている
                    int time = dp[vis][cur] + G[cur][to];
                    if( time <= T[to] ){
                        // 買い物してみる
                        time = max( time, S[to] );
                        time += D[to];
                        int newVis = vis | mask;
                        dp[newVis][to] = min( dp[newVis][to], time );
                    }

                    // 買い物しないで行く
                    dp[vis][to] = min( dp[vis][to], dp[vis][cur] + G[cur][to] );
                }
            }
        }

        return res;
    }
}