SRM579 Div1 Medium(450) TravellingPurchasingMan

TopCoder

TravellingPurchasingMan

bitDP。まず、先頭M店の全点対間最短路を求める。Mは高々16なので、行った店と現在いる店ごとに、その状態になる最も早い時刻を覚えておく。

#include <sstream>
#include <string>
#include <vector>
using namespace std;

int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

class TravellingPurchasingMan{public:
int maxStores( int N, vector <string> interestingStores, vector <string> roads )
{
    int INF = 1000000000;

    //  店の間の最短距離
    vector<vector<int> > D;
    D = vector<vector<int> >(N,vector<int>(N,INF));
    for ( int i=0; i<(int)roads.size(); i++ )
    {
        stringstream ss(roads[i]);
        int A,B,L;
        ss>>A>>B>>L;
        D[A][B] = D[B][A] = L;
    }
    for ( int i=0; i<N; i++ )
        D[i][i] = 0;
    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
    for ( int k=0; k<N; k++ )
        D[j][k] = min(D[j][k],D[j][i]+D[i][k]);

    int M = (int)interestingStores.size();
    vector<int> open(M);
    vector<int> close(M);
    vector<int> duration(M);
    for ( int i=0; i<M; i++ )
    {
        stringstream ss(interestingStores[i]);
        ss>>open[i]>>close[i]>>duration[i];
    }

    //  [i][j]: iのbitが立っている店の商品を買って店jに行く最早時刻
    vector<vector<int> > T(1<<M,vector<int>(M,INF));

    for ( int i=0; i<M; i++ )
        if ( D[N-1][i]<=close[i] )
            T[1<<i][i] = max(D[N-1][i],open[i])+duration[i];

    for ( int bn=1; bn<M; bn++ )
    for ( int b=0; b<(1<<M); b++ )
    if ( countbit(b)==bn )
    for ( int p=0; p<M; p++ )
        for ( int i=0; i<M; i++ )
            if ( T[b][p]+D[p][i]<=close[i] )
                T[b|1<<i][i] = min(T[b|1<<i][i],
                    max(T[b][p]+D[p][i],open[i])+duration[i]);

    int ans = 0;
    for ( int b=0; b<(1<<M); b++ )
    for ( int p=0; p<M; p++ )
        if ( T[b][p]<INF )
            ans = max( ans, countbit(b) );
    return ans;
}};