ソースコード
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
#include <random>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;
template <class T> struct Dijkstra {
struct Edge{
int to;
T cost;
Edge(int _to, T _cost) : to(_to), cost(_cost) {}
};
const T INF_T = numeric_limits<T>::max() / 2;
vector< vector< Edge > > G;
vector< T > d;
Dijkstra (int n) : G(n), d(n) {}
void add_directed_edge(int a, int b, T c) {
G[a].push_back(Edge(b,c));
}
void add_undirected_edge(int a, int b, T c) {
G[a].push_back(Edge(b,c));
G[b].push_back(Edge(a,c));
}
void init(int s) {
priority_queue< pair<T,int>,vector< pair<T,int> >, greater< pair<T,int> > > que;
for (int i = 0; i < d.size(); i++) d[i] = INF_T;
d[s] = 0;
que.push(make_pair(0,s));
while (!que.empty()){
pair<T,int> p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); i++) {
Edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(make_pair(d[e.to],e.to));
}
}
}
}
T dist(int a) {
return d[a];
}
};
int H,W,y,x;
vector<int> yc,xc;
int yl,yr,xl,xr;
Dijkstra<int> inst(1003010);
int idx(int i, int j) {
return i + j * 1001;
}
int main() {
cin >> H >> W >> y >> x;
yc.resize(H+1);
xc.resize(W+1);
REP(i,H) cin >> yc[i+1];
REP(i,W) cin >> xc[i+1];
cin >> yl >> yr >> xl >> xr;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (yl <= i && i <= yr && xl <= j && j <= xr) continue;
if (i != H && !(yl <= i + 1 && i + 1 <= yr && xl <= j && j <= xr))
inst.add_directed_edge(idx(i,j),idx(i+1,j),xc[j]);
if (i != 1 && !(yl <= i - 1 && i - 1 <= yr && xl <= j && j <= xr))
inst.add_directed_edge(idx(i,j),idx(i-1,j),xc[j]);
if (j != W && !(xl <= j + 1 && j + 1 <= xr && yl <= i && i <= yr))
inst.add_directed_edge(idx(i,j),idx(i,j+1),yc[i]);
if (j != 1 && !(xl <= j - 1 && j - 1 <= xr && yl <= i && i <= yr))
inst.add_directed_edge(idx(i,j),idx(i,j-1),yc[i]);
}
}
inst.init(idx(1,1));
int ans = inst.dist(idx(y,x));
if(ans == inst.INF_T) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
/*
int main() {
ll N,L,R; cin >> N >> L >> R;
ll cnt[26] = {};
ll tmp[26] = {};
REP(i,N) {
string s;
ll v;
cin >> s >> v;
REP(j,26) tmp[j] = cnt[j];
REP(j,s.size()) tmp[s[j]-'a']++;
REP(j,26) cnt[j] += v * cnt[j];
}
REP(i,26) cout << cnt[i] << (i < 25 ? " " : "\n");
return 0;
}
*/