結果

問題 No.34 砂漠の行商人
ユーザー kyuridenamidakyuridenamida
提出日時 2016-02-11 10:37:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,370 ms / 5,000 ms
コード長 1,323 bytes
コンパイル時間 1,142 ms
コンパイル使用メモリ 149,884 KB
実行使用メモリ 90,224 KB
最終ジャッジ日時 2023-09-10 19:22:40
合計ジャッジ時間 18,300 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
73,856 KB
testcase_01 AC 25 ms
73,900 KB
testcase_02 AC 74 ms
74,508 KB
testcase_03 AC 29 ms
73,860 KB
testcase_04 AC 307 ms
75,736 KB
testcase_05 AC 394 ms
75,424 KB
testcase_06 AC 287 ms
81,924 KB
testcase_07 AC 628 ms
78,252 KB
testcase_08 AC 802 ms
79,580 KB
testcase_09 AC 721 ms
78,192 KB
testcase_10 AC 1,370 ms
90,224 KB
testcase_11 AC 751 ms
74,116 KB
testcase_12 AC 344 ms
77,724 KB
testcase_13 AC 1,289 ms
79,108 KB
testcase_14 AC 1,197 ms
78,908 KB
testcase_15 AC 360 ms
75,692 KB
testcase_16 AC 337 ms
75,504 KB
testcase_17 AC 773 ms
77,940 KB
testcase_18 AC 84 ms
74,424 KB
testcase_19 AC 1,284 ms
77,848 KB
testcase_20 AC 1,218 ms
78,420 KB
testcase_21 AC 71 ms
75,492 KB
testcase_22 AC 1,193 ms
82,544 KB
testcase_23 AC 491 ms
75,696 KB
testcase_24 AC 1,146 ms
78,524 KB
testcase_25 AC 645 ms
78,948 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0 ; (i) < (int)(n) ; (i)++)
#define REP(i,a,b) for(int (i) = a ; (int)(i) <= (int)(b) ; (i)++)
#define all(n) (n).begin(),(n).end()
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<long long,long long> Pii;
typedef vector<Pii> VPii;


int done[100][100][1802];
int L[100][100];
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};

struct NODE{
	int x,y,c,h;
};
bool operator < (const NODE &a,const NODE &b){
	return a.h < b.h;
}

int main(){
	int N,V,Sx,Sy,Gx,Gy;
	cin >> N >> V >> Sx >> Sy >> Gx >> Gy;
	Sx--,Sy--;
	Gx--,Gy--;
	rep(i,N) rep(j,N) cin >> L[i][j];
	
	rep(i,100)rep(j,100)rep(k,1802) done[i][j][k] = -1e9;
	
	priority_queue<NODE> Q;
	Q.push({Sx,Sy,0,V});
	done[Sy][Sx][0] = V;
	
	unsigned int ans = -1;
	while( Q.size() ){
		auto q = Q.top(); Q.pop();
		if( q.h <= 0 ) continue;
		if( q.c > 1800 ) continue;
		if( done[q.y][q.x][q.c] != q.h ) continue;
		if( q.y == Gy && q.x == Gx ){
			ans = min(ans,(unsigned)q.c);
			continue;
		}
		rep(i,4){
			int tx = q.x + dx[i];
			int ty = q.y + dy[i];
			if( tx < 0 || ty < 0 || ty >= N || tx >= N ) continue;
			if( done[ty][tx][q.c+1] < q.h-L[ty][tx] ){
				done[ty][tx][q.c+1] = q.h-L[ty][tx];
				Q.push({tx,ty,q.c+1,q.h-L[ty][tx]});
			}
		}
	}
	cout << (int) ans << endl;
	
}
0