SRM471 Div1 Medium(500) ThirteenHard

ThirteenHard

今3番目の駅に居るとして、
(T₁+T₂+T₃)%13=a,
(T₂+T₃)%13=b,
(T₃)%13=c,
とすると、
(T₁+T₂+T₃+T₄)%13=(a+T₄)%13,
(T₂+T₃+T₄)%13=(b+T₄)%13,
(T₃+T₄)%13=(c+T₄)%13,
である。
駅の番号と、各駅からその駅までの距離を13で割った余りのビット表現を合わせて１つのノードとした最短経路問題を解く。
最短路が通る辺の数に比べてノード数が多いので、ソートも無しの単純なダイクストラでは間に合わなかったけど、ベルマン・フォードっぽい方法はOKだった。

#include <string>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

class ThirteenHard
{
    int time( char c );
public:
    int calcTime( vector <string> city );
};

int ThirteenHard::time( char c )
{
    if ( 'A' <= c  &&  c <= 'Z' )  return c - 'A' + 1;
    if ( 'a' <= c  &&  c <= 'z' )  return c - 'a' + 27;
    return -1;
}

int ThirteenHard::calcTime( vector <string> city )
{
    int N = (int)city.size();

    vector<vector<int> > T( N, vector<int>( 1<<13, INT_MAX ) );
    vector<vector<bool> > F( N, vector<bool>( 1<<13, false ) );
    T[0][0] = 0;
    F[0][0] = true;

    bool update;
    do
    {
        update = false;

        for ( int fc=0; fc<N; fc++ )
        for ( int fr=0; fr<1<<13; fr++ )
        if ( F[fc][fr] )
        {
            for ( int tc=0; tc<N; tc++ )
            {
                int t = time( city[fc][tc] );
                if ( t >= 0 )
                {
                    int tr = 1<<(t%13);
                    for ( int i=0; i<13; i++ )
                        tr |= (fr>>i&1)<<((i+t)%13);

                    if ( (tr&1) == 0  &&
                         T[tc][tr] > T[fc][fr] + t )
                    {
                        update = true;
                        T[tc][tr] = T[fc][fr] + t;
                        F[tc][tr] = true;
                    }
                }
            }

            F[fc][fr] = false;
        }
    } while ( update );

    int ans = *min_element( T[N-1].begin(), T[N-1].end() );

    return ans<INT_MAX ? ans : -1;
}