SRM471 Div2 Hard(1000) Thirteen

Thirteen

Div1 Mediumとの違いは、経路上の任意の２駅間ではなく最初の駅からの任意の駅までの時間のみが13の倍数にならないこと。
駅の番号と、その駅に到達する時刻を13で割った余りを合わせて１つのノードとした最短経路問題。

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

using namespace std;

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

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

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

    vector<vector<int> > T( N, vector<int>( 13, INT_MAX ) );
    vector<vector<bool> > F( N, vector<bool>( 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<13; fr++ )
        if ( F[fc][fr] )
        {
            for ( int tc=0; tc<N; tc++ )
            {
                int t = time( city[fc][tc] );
                if ( t >= 0 )
                {
                    int tr = ( T[fc][fr] + t ) % 13;

                    if ( tr != 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;
}