結果

提出番号 2375
提出者 kya
言語 C++
提出日時 2020-04-27 22:24:28
問題名 (44)玉ねぎの収穫をするkotamanegi
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 77ms 50688KB
2 AC 100% 57ms 46112KB
3 AC 100% 142ms 90944KB
4 AC 100% 137ms 101536KB
5 AC 100% 106ms 67280KB
6 AC 100% 461ms 229568KB
7 AC 100% 6ms 9520KB
8 AC 100% 156ms 93344KB
9 AC 100% 136ms 85120KB
10 AC 100% 126ms 88896KB
11 AC 100% 113ms 76112KB
12 AC 100% 23ms 21200KB
13 AC 100% 163ms 112544KB
14 AC 100% 51ms 44240KB
15 AC 100% 488ms 251456KB
16 AC 100% 15ms 15440KB
17 AC 100% 116ms 85696KB
18 AC 100% 120ms 86672KB
19 AC 100% 126ms 83312KB
20 AC 100% 11ms 13136KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Edge {
    int to; T cost;
    Edge (int to, T cost = 1) : to(to), cost(cost) { }
    bool operator< (const Edge &r) const { return (cost < r.cost); }
};

template<typename T>
using Graph = vector<vector<Edge<T>>>;

template <typename T>
vector<T> dijkstra(const Graph<T> &g, int s){
    using P = pair<T, int>;
    vector<T> ret(g.size(), -1);
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(ret[s], s); ret[s] = 0;
    while (not que.empty()) {
        int v; T c; tie(c, v) = que.top(); que.pop();
        if (ret[v] < c) continue;
        for (const auto &e : g[v]) {
            if (ret[e.to] > ret[v] + e.cost or ret[e.to] == -1) {
                ret[e.to] = ret[v] + e.cost;
                que.emplace(ret[e.to], e.to);
            }
        }
    }
    return ret;
}

int main() {
    int h, w, s, t, yl, yr, xl, xr;
    cin >> h >> w >> s >> t;
    vector<int> y(h), x(w);
    for (int &e : y) cin >> e;
    for (int &e : x) cin >> e;
    cin >> yl >> yr >> xl >> xr;
    s--; t--; yl--; yr--; xl--; yr--;

    auto check = [&] (int i, int j) -> bool {
        if (i < 0 or j < 0 or h <= i or w <= j) return false;
        if (yl <= i and i <= yr and xl <= j and j <= xr) return false;
        return true;
    };

    auto index = [&] (int i, int j) -> int {
        return i * w + j;
    };

    Graph<int> g(h * w);

    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (not check(i, j)) continue;
        for (int delta : {1, -1}) {
            const int di = i + delta, dj = j + delta;
            if (check(di, j)) g[index(i, j)].emplace_back(index(di, j), x[j]);
            if (check(i, dj)) g[index(i, j)].emplace_back(index(i, dj), y[i]);
        }
    }

    vector<int> ans = dijkstra(g, 0);

    cout << ans[index(s, t)] << '\n';

    return 0;
}