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

dp[ i ][ j ][ t ] : 到達 ( i, j ) 時，有無使用過炸彈( t )，此時最小的總值

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;
}
```