ソースコード
#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;
}