結果

問題 No.34 砂漠の行商人
ユーザー ytftytft
提出日時 2022-11-04 20:52:39
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 922 bytes
コンパイル時間 2,785 ms
コンパイル使用メモリ 252,744 KB
実行使用メモリ 248,576 KB
最終ジャッジ日時 2024-07-18 18:42:04
合計ジャッジ時間 10,132 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 9 ms
5,376 KB
testcase_04 AC 50 ms
6,272 KB
testcase_05 AC 48 ms
6,656 KB
testcase_06 AC 5 ms
5,376 KB
testcase_07 AC 78 ms
7,552 KB
testcase_08 AC 114 ms
9,856 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int main(){
	int N,V,S[2],G[2],ans=INT_MAX,d[4][2];
	for(int i=0;i<4;++i){
		for(int j=0;j<2;++j){
			d[i][j]=((i+j)%2)*((i/2)*2-1);
		}
	}
	scanf("%d%d%d%d%d%d",&N,&V,S,S+1,G,G+1);
	int L[N][N],dist[N][N][V];
	queue<vector<int>> que;
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			scanf("%d",&L[i][j]);
			for(int k=0;k<V;++k){
				dist[i][j][k]=INT_MAX;
			}
		}
	}
	que.push({S[1]-1,S[0]-1,V-1,0});
	while(!que.empty()){
		vector<int> cur=que.front();
		que.pop();
		if(cur[2]<0||cur[0]>=N||cur[0]<0||cur[1]>=N||cur[1]<0){
			continue;
		}
		if(dist[cur[0]][cur[1]][cur[2]]<=cur[3]){
			continue;
		}
		dist[cur[0]][cur[1]][cur[2]]=cur[3];
		for(int i=0;i<4;++i){
			que.push({cur[0]+d[i][0],cur[1]+d[i][1],cur[2]-L[cur[0]+d[i][0]][cur[1]+d[i][1]],cur[3]+1});
		}
	}
	for(int i=0;i<V;++i){
		ans=min(ans,dist[G[1]-1][G[0]-1][i]);
	}
	printf("%d\n",ans<INT_MAX?ans:-1);
}
0