# Yuki 34 砂漠の行商人 ( Dummy Constraints )

No.34 砂漠の行商人 - yukicoder

```int N, V, Sx, Sy, Gx, Gy;
vvi LV;

void init(){
cin >> N >> V >> Sx >> Sy >> Gx >> Gy;
upmin( V, 1800 - 1 );
--Sx, --Sy, --Gx, --Gy;
swap( Sx, Sy ), swap( Gx, Gy );
LV = vvi( N, vi( N ) );
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
cin >> LV[ i ][ j ];
}

int dis[ 1800 ][ 100 ][ 100 ];

void solve(){
memset( dis, INF, sizeof( dis ) );
typedef tuple< int, int, int, int > t4i;
queue< t4i > que;
que.emplace( dis[ V ][ Sx ][ Sy ] = 0, V, Sx, Sy );
while( not que.empty() ){
int d, v, x, y; tie( d, v, x, y ) = que.front(); que.pop();
if( dis[ v ][ x ][ y ] != d ) continue;
if( x == Gx and y == Gy )
cout << d << endl, exit( 0 );
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
for( int di = 0; di < 4; ++di ){
int nx = x + dx[ di ];
int ny = y + dy[ di ];
if( not ( 0 <= nx and nx < N and 0 <= ny and ny < N ) ) continue;
if( v - LV[ nx ][ ny ] <= 0 ) continue;
if( upmin( dis[ v - LV[ nx ][ ny ] ][ nx ][ ny ], dis[ v ][ x ][ y ] + 1 ) )
que.emplace( dis[ v - LV[ nx ][ ny ] ][ nx ][ ny ], v - LV[ nx ][ ny ], nx, ny );
}
}
cout << -1 << endl;
}
```