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 <cstdio>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 25e4 + 10, M = 2e6 + 10, inf = 2e6;
bool vis[N];
int n, st, ed, d[N];
int idx, hd[N], nxt[M], edg[M], wt[M];
int num(int x, int y)
{
return (x - 1) * n + y;
}
void add(int a, int b, int c)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
wt[idx] = c;
}
int main()
{
scanf("%d", &n);
st = 0;
ed = n * n + 1;
for (int i = st; i <= ed; i++)
hd[i] = -1;
for (int i = 1, a; i <= n + 1; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &a);
int x = num(i, j), y = num(i - 1, j);
if (i == 1)
add(st, x, a);
else if (i == n + 1)
add(y, ed, a);
else
add(y, x, a);
}
for (int i = 1, a; i <= n; i++)
for (int j = 1; j <= n + 1; j++)
{
scanf("%d", &a);
int x = num(i, j), y = num(i, j - 1);
if (j == 1)
add(x, ed, a);
else if (j == n + 1)
add(st, y, a);
else
add(x, y, a);
}
for (int i = 1, a; i <= n + 1; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &a);
int x = num(i, j), y = num(i - 1, j);
if (i == 1)
add(x, st, a);
else if (i == n + 1)
add(ed, y, a);
else
add(x, y, a);
}
for (int i = 1, a; i <= n; i++)
for (int j = 1; j <= n + 1; j++)
{
scanf("%d", &a);
int x = num(i, j), y = num(i, j - 1);
if (j == 1)
add(ed, x, a);
else if (j == n + 1)
add(y, st, a);
else
add(y, x, a);
}
for (int i = st; i <= ed; i++)
d[i] = inf;
d[st] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push(make_pair(0, st));
while (!q.empty())
{
int t = q.top().second;
q.pop();
if (vis[t])
continue;
vis[t] = true;
for (int i = hd[t]; ~i; i = nxt[i])
if (d[t] + wt[i] < d[edg[i]])
{
d[edg[i]] = d[t] + wt[i];
q.push(make_pair(d[edg[i]], edg[i]));
}
}
printf("%d", d[ed]);
return 0;
}
|
