結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-22 22:02:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,513 bytes |
コンパイル時間 | 2,240 ms |
コンパイル使用メモリ | 200,524 KB |
最終ジャッジ日時 | 2025-02-20 11:40:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} const ll INF=1LL<<60; ll D[2010][2010]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll H,W; int N; cin>>H>>W>>N; vector<ll>a(N),b(N),c(N),d(N); for(int i=0;i<N;i++)cin>>a[i]>>b[i]>>c[i]>>d[i]; vector<ll>X(2*N+2),Y(2*N+2); X[0]=1,Y[0]=1; for(int i=0;i<N;i++){ X[2*i+1]=a[i],Y[2*i+1]=b[i]; X[2*i+2]=c[i],Y[2*i+2]=d[i]; } X[2*N+1]=H,Y[2*N+1]=W; for(int i=0;i<=2*N+1;i++)for(int j=0;j<=2*N+1;j++)D[i][j]=INF; for(int i=0;i<N;i++){ D[2*i+1][2*i+2]=1LL; } for(int i=0;i<=2*N+1;i++){ for(int j=0;j<=2*N+1;j++){ if(i==j)continue; chmin(D[i][j],abs(X[i]-X[j])+abs(Y[i]-Y[j])); } } vector<ll>dist(2*N+2,INF); dist[0]=0LL; priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq; pq.push(make_pair(dist[0],0)); while(pq.size()){ auto[c,x]=pq.top(); pq.pop(); if(dist[x]<c)continue; for(int i=0;i<=2*N+1;i++){ if(i==x)continue; if(chmin(dist[i],c+D[x][i])){ pq.push(make_pair(dist[i],i)); } } } cout<<dist[2*N+1]<<"\n"; }