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

No.34 砂漠の行商人 - yukicoder

最悪の場合は通る砂漠のレベルが全部最高である 9のとき。この場合は遠回りはいらないのでマンハッタン距離を考えて、体力は精々 N * 2 * 9 で十分だと分くる。

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