CFR 386 D. Game with Points ( Dijkstra )

Problem - D - Codeforces

dp[ i ][ j ][ k ] : number of minimum moves for a state described by ( i, j, k ), i < j < k, where the three stones are located in each of them

int N;
int dp[ MAXN ][ MAXN ][ MAXN ];
pii move[ MAXN ][ MAXN ][ MAXN ];
vi pre[ MAXN ][ MAXN ][ MAXN ];
string edge[ MAXN ];

typedef pair< int, vi > pivi;

void solve(){
    cin >> N;
    memset( dp, INF, sizeof( dp ) );
    vi stone( 3 );
    for( int i = 0; i < 3; ++i )
        cin >> stone[ i ],
        --stone[ i ];
    sort( stone.begin(), stone.end() );
    dp[ stone[ 0 ] ][ stone[ 1 ] ][ stone[ 2 ] ] = 0;
    for( int i = 0; i < N; ++i )
        cin >> edge[ i ];
    vi goal = { 0, 1, 2 };
    priority_queue< pivi, vector< pivi >, greater< pivi > > pq;
    pq.push( pivi( 0, stone ) );
    while( not pq.empty() ){
        int d = pq.top().first;
        vi t = pq.top().second;
        pq.pop();
        if( dp[ t[ 0 ] ][ t[ 1 ] ][ t[ 2 ] ] != d )
            continue;
        for( int i = 0; i < 3; ++i )
            for( int x = 0; x < N; ++x )
                if( t[ 0 ] != x and t[ 1 ] != x and t[ 2 ] != x ){
                    if( i == 0 ){
                        vi nt = { t[ 1 ], t[ 2 ], x };
                        sort( nt.begin(), nt.end() );
                        if( edge[ t[ 0 ] ][ x ] == edge[ t[ 1 ] ][ t[ 2 ] ] )
                            if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) )
                                move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ),
                                pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t,
                                pq.push( pivi( d + 1, nt ) );
                    } else if( i == 1 ){
                        vi nt = { t[ 0 ], t[ 2 ], x };
                        sort( nt.begin(), nt.end() );
                        if( edge[ t[ 1 ] ][ x ] == edge[ t[ 0 ] ][ t[ 2 ] ] )
                            if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) )
                                move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ),
                                pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t,
                                pq.push( pivi( d + 1, nt ) );
                    } else{
                        vi nt = { t[ 0 ], t[ 1 ], x };
                        sort( nt.begin(), nt.end() );
                        if( edge[ t[ 2 ] ][ x ] == edge[ t[ 0 ] ][ t[ 1 ] ] )
                            if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) )
                                move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ),
                                pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t,
                                pq.push( pivi( d + 1, nt ) );
                    }
                }
    }
    vp ans;
    for( vi u = goal; ; ){
        vi pu = pre[ u[ 0 ] ][ u[ 1 ] ][ u[ 2 ] ];
        if( pu.empty() ) break;
        ans.push_back( move[ u[ 0 ] ][ u[ 1 ] ][ u[ 2 ] ] );
        u = pu;
    }
    if( dp[ goal[ 0 ] ][ goal[ 1 ] ][ goal[ 2 ] ] == INF )
        cout << -1 << endl;
    else{
        cout << ans.size() << endl;
        for( int i = ans.size() - 1; i >= 0; --i )
            cout << ans[ i ].first + 1 << " " << ans[ i ].second + 1 << "\n";
    }
}