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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(int i = 0; i < (n); i++)
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
const int maxn = 1e3 + 10;
int n, m;
int cost[maxn][maxn][3];
struct edge
{
int from, to, dist;
};
int ID(int half, int x, int y) {
return x * m + y + 1 + half * n*m;
}
struct HeapNode
{
int d, u;
bool operator<(const HeapNode& rhs)const {
return d > rhs.d;
}
};
struct Dij
{
int n, m;
vector<edge>edges;
vector<int>G[N];
bool done[N];
int d[N];
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++)G[i].clear();
edges.clear();
}
void add_edge(int u, int v, int w) {
edges.push_back(edge{ u,v,w });
G[u].push_back(edges.size() - 1);
edges.push_back(edge{ v,u,w });
G[v].push_back(edges.size() - 1);
}
void dij(int s) {
priority_queue<HeapNode>Q;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
memset(done, 0, sizeof(done));
Q.push(HeapNode{ 0,s });
while (!Q.empty()) {
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if (done[u])continue;
done[u] = true;
REP(i, G[u].size()) {
edge& e = edges[G[u][i]];
if (d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
Q.push(HeapNode{ d[e.to],e.to });
}
}
}
}
}sol;
int tt = 0;
int main() {
while (scanf("%d%d", &n, &m) && n) {
tt++;
int T = 2 * n*m+1;
sol.init(T);
REP(i, n)REP(j, m - 1)scanf("%d", &cost[i][j][0]);
REP(i, n - 1)REP(j, m)scanf("%d", &cost[i][j][1]);
REP(i, n - 1)REP(j, m - 1)scanf("%d", &cost[i][j][2]);
REP(i, n - 1){
sol.add_edge(0, ID(0, i, 0), cost[i][0][1]);
sol.add_edge(T, ID(1, i, m - 2), cost[i][m - 1][1]);
}
REP(i, m - 1) {
sol.add_edge(0, ID(0, n - 2, i), cost[n - 1][i][0]);
sol.add_edge(T, ID(1, 0, i), cost[0][i][0]);
}
REP(i, n - 1)REP(j, m - 1) {
int u = ID(0, i, j);
if (i < n - 2)sol.add_edge(u, ID(1, i + 1, j), cost[i + 1][j][0]);
int v = ID(1, i, j);
if (j < m - 2)sol.add_edge(v, ID(0, i, j + 1), cost[i][j + 1][1]);
sol.add_edge(u, v, cost[i][j][2]);
}
sol.dij(0);
printf("Case %d: Minimum = %d\n", tt, sol.d[T]);
}
return 0;
}
|
