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
| #include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0;
bool flag = 0;
char c = getchar();
while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
if (res < 0) putchar('-'), res = -res;
if (res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 1005, M = 3e6 + 5;
int n, m;
int hen[N][N], zong[N][N], xie[N][N];
int idx;
int e[M << 1], ne[M << 1], h[M << 1], w[M << 1];
inline void add(int x, int y, int z)
{
idx ++;
e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
}
inline void addage(int x, int y, int z)
{
add(x, y, z), add(y, x, z);
}
int cnt, S, T;
inline int id(int x, int y)
{
return (x - 1) * (m - 1) * 2 + y * 2 - 1;
}
int vis[M << 1], dis[M << 1];
inline void calc()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(dis, 0x3f, sizeof(dis));
q.push({0, S});
dis[S] = 0;
while(!q.empty())
{
PII o = q.top(); q.pop();
if(vis[o.second]) continue;
vis[o.second] = 1;
for(int i = h[o.second], j; ~i;i = ne[i])
{
j = e[i];
if(dis[j] > dis[o.second] + w[i])
dis[j] = dis[o.second] + w[i], q.push({dis[j], j});
}
}
}
int main()
{
memset(h, -1, sizeof(h));
read(n, m);
T = 2 * n * m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j < m;j ++) read(hen[i][j]);
for(int i = 1;i < n;i ++)
for(int j = 1;j <= m;j ++) read(zong[i][j]);
for(int i = 1;i < n;i ++)
for(int j = 1;j < m;j ++) read(xie[i][j]);
for(int i = 1;i < n;i ++)
for(int j = 1, l, r;j < m;j ++)
{
l = cnt + 1, r = cnt + 2;
cnt += 2;
addage(l, r, xie[i][j]);
if(j != 1) addage(l, l - 1, zong[i][j]);
else addage(S, l, zong[i][j]);
if(i != 1) addage(r, id(i - 1, j), hen[i][j]);
else addage(r, T, hen[i][j]);
if(i == n - 1) addage(S, l, hen[i + 1][j]);
if(j == m - 1) addage(r, T, zong[i][j + 1]);
}
calc();
write(dis[T]);
return 0;
}
|
