1 /**************************************************************  2     Problem: 1001  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:520 ms  7     Memory:94588 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 #include <queue> 14   15 using namespace std; 16   17 struct edges{ 18     int next, to, v; 19 } e[6000005]; 20   21 struct heap_node{ 22     int v, to; 23 }; 24 inline bool operator < (const heap_node &a, const heap_node &b){ 25     return a.v > b.v; 26 } 27   28 priority_queue <heap_node> h; 29 heap_node NODE; 30 int tot, S, T, n, m; 31 int d[3000005], first[3000005]; 32 char ch; 33   34 inline int read(){ 35     int x = 0, sgn = 1; 36     ch = getchar(); 37     while (ch < ‘0‘ || ch > ‘9‘){ 38         if (ch == ‘-‘) sgn = -1; 39         ch = getchar(); 40     } 41     while (ch >= ‘0‘ && ch <= ‘9‘){ 42         x = x * 10 + ch - ‘0‘; 43         ch = getchar(); 44     } 45     return sgn * x; 46 } 47   48 inline void add_edge(int x, int y, int v){ 49     e[++tot].next = first[x], first[x] = tot; 50     e[tot].to = y, e[tot].v = v; 51 } 52   53 void add_Edges(const int x, const int y, const int v){ 54     add_edge(x, y, v); 55     add_edge(y, x, v); 56 } 57   58 inline void add_to_heap(const int p){ 59     for (int x = first[p]; x; x = e[x].next) 60         if (d[e[x].to] == -1){ 61             NODE.v = e[x].v + d[p], NODE.to = e[x].to; 62             h.push(NODE); 63         } 64 } 65   66 int Dijkstra(int S, int T){ 67     memset(d, -1, sizeof(d)); 68     while (!h.empty()) h.pop(); 69     d[S] = 0, add_to_heap(S); 70     int p; 71     while (d[T] == -1){ 72         while (d[h.top().to] != -1) h.pop(); 73         p = h.top().to; 74         d[p] = h.top().v; 75         h.pop(); 76         add_to_heap(p); 77     } 78     return d[T]; 79 } 80   81 void build_graph(){ 82     int Cost, x, y; 83     for (int i = 1; i <= n; ++i) 84         for (int j = 1; j < m; ++j){ 85             Cost = read(); 86             x = i == 1 ? S : (2 * i - 3) * (m - 1) + j; 87             y = i == n ? T : (2 * i - 2) * (m - 1) + j; 88             add_Edges(x, y, Cost); 89         } 90     for (int i = 1; i < n; ++i) 91         for (int j = 1; j <= m; ++j){ 92             Cost = read(); 93             x = j == 1 ? T : 2 * (i - 1) * (m - 1) + j - 1; 94             y = j == m ? S : 2 * (i - 1) * (m - 1) + j - 1 + m; 95             add_Edges(x, y, Cost); 96         } 97     for (int i = 1; i < n; ++i) 98         for (int j = 1; j < m; ++j){ 99             Cost = read();100             x = (2 * i - 2) * (m - 1) + j;101             y = (2 * i - 1) * (m - 1) + j;102             add_Edges(x, y, Cost);103         }104 }105  106 int main(){107     n = read(), m = read();108     if (n == 1 && m == 1){109         printf("%d\n", 0);110         return 0;111     }112      113     S = 0, T = 2 * (m - 1) * (n - 1) + 1;114     build_graph();         115     printf("%d\n", Dijkstra(S, T));116     return 0;117 }