台北市104 學年度資訊學科能力競賽 pE. Saving Ryan( DP )

dp[ i ][ j ][ t ] : 到達 ( i, j ) 時，有無使用過炸彈( t )，此時最小的總值
因為可以上下左右彎來彎去，所以用 dijkstra 更新。
tuple 真好用。

#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;

const int INF = 0x3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
    if( x < v ){
        x = v;
        return 1;
    }
    return 0;
}

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
    if( x > v ){
        x = v;
        return 1;
    }
    return 0;
}

int N;
vvi mat;
int Q;
vector< tuple< int, int, int, int > > qry;

void init(){
    cin >> N;
    mat = vvi( N, vi( N ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j )
            cin >> mat[ i ][ j ];
    cin >> Q;
    for( int i = 0; i < Q; ++i ){
        int xq0, yq0, xq1, yq1;
        cin >> xq0 >> yq0 >> xq1 >> yq1;
        qry.emplace_back( xq0 - 1, yq0 - 1, xq1 - 1, yq1 - 1 );
    }
}

int in_range( int x, int y ){
    return 0 <= x and x < N and 0 <= y and y < N;
}

void solve(){
    for( int i = 0; i < Q; ++i ){
        int xq0, yq0, xq1, yq1;
        tie( xq0, yq0, xq1, yq1 ) = qry[ i ];
        priority_queue< tuple< int, int, int, int >, vector< tuple< int, int, int, int > >,
                        greater< tuple< int, int, int, int > > > pq;
        vvvi dp( N, vvi( N, vi( 2, INF ) ) );
        pq.emplace( dp[ xq0 ][ yq0 ][ 0 ] = mat[ xq0 ][ yq0 ], xq0, yq0, 0 );
        pq.emplace( dp[ xq0 ][ yq0 ][ 1 ] = 0, xq0, yq0, 1 );
        while( not pq.empty() ){
            int v, x, y, t;
            tie( v, x, y, t ) = pq.top();
            pq.pop();
            if( dp[ x ][ y ][ t ] != v )
                continue;
            for( int di = 0; di < 4; ++di ){
                int nx = x + dx[ di ];
                int ny = y + dy[ di ];
                if( not in_range( nx, ny ) )
                    continue;
                if( upmin( dp[ nx ][ ny ][ t ], dp[ x ][ y ][ t ] + mat[ nx ][ ny ] ) )
                    pq.emplace( dp[ nx ][ ny ][ t ], nx, ny, t );
                if( not t and upmin( dp[ nx ][ ny ][ 1 ], dp[ x ][ y ][ t ] ) )
                    pq.emplace( dp[ nx ][ ny ][ 1 ], nx, ny, 1 );
            }
        }
        cout << dp[ xq1 ][ yq1 ][ 1 ] << endl;
    }
}

signed main(){
    ios::sync_with_stdio( false );
    init();
    solve();
    return 0;
}