結果
問題 | No.34 砂漠の行商人 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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);}