結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-22 21:36:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 853 bytes |
コンパイル時間 | 571 ms |
コンパイル使用メモリ | 66,276 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 11:03:18 |
合計ジャッジ時間 | 1,506 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<iostream> #include<cassert> using namespace std; int H,W,N; int a[1000],b[1000],c[1000],d[1000]; int x[2002],y[2002]; long dist[2002]; bool vis[2002]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>H>>W>>N; for(int i=0;i<N;i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; x[i]=a[i],y[i]=b[i]; x[N+i]=c[i],y[N+i]=d[i]; } x[2*N]=1,y[2*N]=1; x[2*N+1]=H,y[2*N+1]=W; for(int i=0;i<2*N+2;i++)dist[i]=1e18; dist[2*N]=0; while(true) { int mi=-1; for(int i=0;i<2*N+2;i++)if(!vis[i]) { if(mi==-1||dist[mi]>dist[i])mi=i; } if(mi==-1)break; vis[mi]=true; for(int j=0;j<2*N+2;j++) { long d=dist[mi]; d+=abs(x[mi]-x[j]); d+=abs(y[mi]-y[j]); if(dist[j]>d) { dist[j]=d; } } if(mi<N) { long d=dist[mi]+1; if(dist[mi+N]>d) { dist[mi+N]=d; } } } cout<<dist[2*N+1]<<endl; }