結果

問題 No.34 砂漠の行商人
ユーザー ytftytft
提出日時 2022-11-04 21:05:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,006 ms / 5,000 ms
コード長 1,045 bytes
コンパイル時間 2,445 ms
コンパイル使用メモリ 253,292 KB
実行使用メモリ 61,568 KB
最終ジャッジ日時 2024-07-18 18:52:48
合計ジャッジ時間 6,858 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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);
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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0