結果

問題 No.2695 Warp Zone
コンテスト
ユーザー taipika
提出日時 2024-03-22 22:09:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,732 bytes
コンパイル時間 4,490 ms
コンパイル使用メモリ 247,160 KB
実行使用メモリ 13,952 KB
最終ジャッジ日時 2024-09-30 11:38:25
合計ジャッジ時間 10,305 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

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>,bool> 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])]=true;
    }
    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) {
            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) {
            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) {
            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) {
            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-1,s-1}]) {
        q.push({fmp[{f-1,s-1}],smp[{f-1,s-1}]});
        mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]]=min(mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]],mint[f-1][s-1]+1);
        }

    }

    cout << mint[h-1][w-1] << endl;
    
}
0