結果

問題 No.2695 Warp Zone
ユーザー taipikataipika
提出日時 2024-03-23 07:38:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,783 bytes
コンパイル時間 4,495 ms
コンパイル使用メモリ 281,192 KB
実行使用メモリ 818,176 KB
最終ジャッジ日時 2024-09-30 13:06:38
合計ジャッジ時間 6,546 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 MLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
//    }
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;
    for (int i=0;i<n;i++) {
        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;

}
0