1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #define maxn 205
int n,m,T;
int head=1,h[maxn*maxn];
inline int id(int x,int y) {return (x-1)*(m+1)+y;}
struct yyy{
int to,z,w;
inline void add(int x,int y,int val) {
to=y;z=h[x];h[x]=head;w=val;
}
}a[160005];
inline void ins(int x,int y,int z) {
a[++head].add(x,y,z);
a[++head].add(y,x,z);
}
struct node{
int x,xx,y,yy,id;
}tmp;
vector<node>O;
int Ans[100005];
#define fi first
#define se second
#define mk make_pair
priority_queue<pair<int,int > >q;
const int inf=1e9;
int vis[maxn*maxn],dis[maxn][maxn*maxn];
inline void dj(int pos,int x,int y,int Lx,int Rx,int Ly,int Ry) {
int i,j;
assert(pos<=200);
while (!q.empty()) q.pop();
for (i=Lx;i<=Rx;i++) for (j=Ly;j<=Ry;j++) dis[pos][id(i,j)]=inf,vis[id(i,j)]=0;
dis[pos][id(x,y)]=0;q.push(mk(-dis[pos][id(x,y)],id(x,y)));
while (!q.empty()) {
int tmp=q.top().se;q.pop();
y=tmp%(m+1),x=tmp/(m+1)+1;
if (vis[tmp]) continue;
vis[tmp]=1;
for (i=h[tmp];i;i=a[i].z) if (dis[pos][a[i].to]>dis[pos][tmp]+a[i].w
&&Lx<=a[i].to/(m+1)+1&&a[i].to/(m+1)+1<=Rx&&Ly<=a[i].to%(m+1)&&a[i].to%(m+1)<=Ry) {
dis[pos][a[i].to]=dis[pos][tmp]+a[i].w;
q.push(mk(-dis[pos][a[i].to],a[i].to));
}
}
}
inline void solve(int lx,int rx,int ly,int ry,vector<node>q) {
int i,j;
if (ry-ly+1<=3&&rx-lx+1<=3) {
int tot=0;
for (i=lx;i<=rx;i++)
for (j=ly;j<=ry;j++)
++tot,dj(tot,i,j,lx,rx,ly,ry);
for (auto tmp:q) {
for (i=1;i<=tot;i++)
Ans[tmp.id]=min(Ans[tmp.id],dis[i][id(tmp.x,tmp.y)]+dis[i][id(tmp.xx,tmp.yy)]);
}
return ;
}
if (rx-lx<ry-ly) {
int mid=ly+ry>>1,tot=0;
for (i=lx;i<=rx;i++) dj(++tot,i,mid,lx,rx,ly,ry);
vector<node>ql,qr;
for (auto tmp:q) {
for (i=1;i<=tot;i++) Ans[tmp.id]=min(Ans[tmp.id],dis[i][id(tmp.x,tmp.y)]+dis[i][id(tmp.xx,tmp.yy)]);
if (max(tmp.y,tmp.yy)<=mid) ql.push_back(tmp);
else if (min(tmp.y,tmp.yy)>mid) qr.push_back(tmp);
}
solve(lx,rx,ly,mid,ql);
solve(lx,rx,mid,ry,qr);
}
else {
int mid=lx+rx>>1,tot=0;
for (i=ly;i<=ry;i++) ++tot,dj(tot,mid,i,lx,rx,ly,ry);
vector<node>ql,qr;
for (auto tmp:q) {
for (i=1;i<=tot;i++) Ans[tmp.id]=min(Ans[tmp.id],dis[i][id(tmp.x,tmp.y)]+dis[i][id(tmp.xx,tmp.yy)]);
if (max(tmp.x,tmp.xx)<=mid) ql.push_back(tmp);
else if (min(tmp.x,tmp.xx)>mid) qr.push_back(tmp);
}
solve(lx,mid,ly,ry,ql);
solve(mid,rx,ly,ry,qr);
}
}
signed main(void){
int i,j,x;
read(n);read(m);
memset(Ans,0x3f,sizeof(Ans));
for (i=1;i<=n;i++)
for (j=1;j<m;j++)
read(x),ins(id(i,j),id(i,j+1),x);
for (i=1;i<n;i++)
for (j=1;j<=m;j++)
read(x),ins(id(i,j),id(i+1,j),x);
read(T);node tmp;
for (i=1;i<=T;i++) {
read(tmp.x),read(tmp.y),read(tmp.xx),read(tmp.yy);tmp.id=i;
O.push_back(tmp);
}
solve(1,n,1,m,O);
for (i=1;i<=T;i++) printf("%d\n",Ans[i]);
return 0;
}
|