#813783 (C++23(draft)) No.34 砂漠の行商人

• 問題: No.34 砂漠の行商人
• ユーザー: ytft
• 提出日時: 2022-11-04 21:05:51
• 言語: C++23(draft) (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 3,024 ms / 5,000 ms
• コード長: 1,045 bytes
• コンパイル時間: 3,027 ms
• コンパイル使用メモリ: 252,520 KB
• 実行使用メモリ: 61,556 KB
• 最終ジャッジ日時: 2023-09-25 23:17:20
• 合計ジャッジ時間: 9,437 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	4 ms; 4,380 KB
testcase_03	AC	2 ms; 4,380 KB
testcase_04	AC	52 ms; 6,004 KB
testcase_05	AC	51 ms; 6,652 KB
testcase_06	AC	5 ms; 4,376 KB
testcase_07	AC	82 ms; 7,580 KB
testcase_08	AC	115 ms; 9,784 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,376 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	54 ms; 6,856 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	2 ms; 4,380 KB
testcase_15	AC	2 ms; 4,384 KB
testcase_16	AC	2 ms; 4,384 KB
testcase_17	AC	1 ms; 4,380 KB
testcase_18	AC	2 ms; 4,380 KB
testcase_19	AC	1,538 ms; 41,116 KB
testcase_20	AC	3,024 ms; 61,556 KB
testcase_21	AC	6 ms; 5,720 KB
testcase_22	AC	2 ms; 4,380 KB
testcase_23	AC	2 ms; 4,376 KB
testcase_24	AC	2 ms; 4,380 KB
testcase_25	AC	200 ms; 12,828 KB

ソースコード

#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);
	if((abs(S[0]-G[0])+abs(S[1]-G[1]))*9<=V){
		printf("%d\n",abs(S[0]-G[0])+abs(S[1]-G[1]));
		return 0;
	}
	int L[N+2][N+2],dist[N+2][N+2][V];
	queue<vector<int>> que;
	for(int i=1;i<=N;++i){
		L[i][N+1]=INT_MAX;
		L[i][0]=INT_MAX;
		L[N+1][i]=INT_MAX;
		L[0][i]=INT_MAX;
		for(int j=1;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],S[0],V-1,0});
	while(!que.empty()){
		vector<int> cur=que.front();
		que.pop();
		if(cur[2]<0||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]][G[0]][i]);
	}
	printf("%d\n",ans<INT_MAX?ans:-1);
}