結果

問題 No.2695 Warp Zone
ユーザー taipika
提出日時 2024-03-23 07:45:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,826 bytes
コンパイル時間 6,498 ms
コンパイル使用メモリ 270,860 KB
最終ジャッジ日時 2025-02-20 13:05:36
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
#define all(x) (x).begin(), (x).end()
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    ll s = (ll)v.size();
    for (ll i = 0; i < s; i++) os << (i ? ' ' : ' ') << v[i];
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
//エラトステネスのふるい
bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}
//    map<pair<ll,ll>,bool> mp;
//    rep(i,m) {
//        mp[make_pair(x[i],y[i])]=true;
//    }
#define rep(i, n) for (ll (i) = 0; (i) < (ll)(n); (i)++)
int main() {
    ll h,w,n;
    cin >> h >> w >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> c(n);
    vector<ll> d(n);
    map<pair<ll,ll>,ll> fmp;
    map<pair<ll,ll>,ll> smp;
    map<pair<ll,ll>,int> bmp;
    rep(i,n) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        fmp[make_pair(a[i],b[i])]=c[i];
        smp[make_pair(a[i],b[i])]=d[i];
        bmp[make_pair(a[i],b[i])]=1e9;
    }
    queue<pair<ll,ll>> q;
    vector<vector<ll>> mint(h,vector<ll>(w,1e18));
    mint[0][0]=0;
    q.push(make_pair(1,1));
    while(!q.empty()) {
        ll f=q.front().first;
        ll s=q.front().second;
        q.pop();
        if (f-1>0&&mint[f-2][s-1]==1e18) {
            q.push(make_pair(f-1,s));
            mint[f-2][s-1]=min(mint[f-2][s-1],mint[f-1][s-1]+1);
        }
        if (h-1>=f&&mint[f][s-1]==1e18) {
            q.push(make_pair(f+1,s));
            mint[f][s-1]=min(mint[f][s-1],mint[f-1][s-1]+1);
        }
        if (s-1>0&&mint[f-1][s-2]==1e18) {
            q.push(make_pair(f,s-1));
            mint[f-1][s-2]=min(mint[f-1][s-2],mint[f-1][s-1]+1);
        }
        if (w-1>=s&&mint[f-1][s]==1e18) {
            q.push(make_pair(f,s+1));
            mint[f-1][s]=min(mint[f-1][s],mint[f-1][s-1]+1);
        }
        if (bmp[{f,s}]==1e9&&mint[fmp[{f,s}]-1][smp[{f,s}]-1]) {
        q.push({fmp[{f,s}],smp[{f,s}]});
        mint[fmp[{f,s}]-1][smp[{f,s}]-1]=min(mint[fmp[{f,s}]-1][smp[{f,s}]-1],mint[f-1][s-1]+1);
        }
    }
cout << mint[h-1][w-1] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0