/VM 08 Bài 13 - Bin Laden

              #include <iostream>
        #include <queue>
        using namespace std;
        
        #define INF 1000000000
        
        int m, n;
        int ans = INF;
        int a[3000][20];
        int b[3000][20];
        int d[3000][20];
        
        
        struct Node {
          int x, y, dist;
        
          bool operator < (const Node& other) const {
            return this->dist > other.dist;
          }
        };
        
        priority_queue<Node> iDex;
        
        void up(Node x) {
          int i = x.x, j = x.y, p = x.x - 1, q = x.y;
          if (p >= 0 && d[i][j] + b[i][j] < d[p][q]) {
            d[p][q] = d[i][j] + b[i][j];
            iDex.push({ p, q, d[p][q] });
          }
        }
        
        void down(Node x) {
          int i = x.x, j = x.y, p = x.x + 1, q = x.y;
          if (p <= m && d[i][j] + b[p][q] < d[p][q]) {
            d[p][q] = d[i][j] + b[p][q];
            iDex.push({ p, q, d[p][q] });
          }
        }
        
        void left(Node x) {
          int i = x.x, j = x.y, p = x.x, q = x.y - 1;
          if (q >= 1 && d[i][j] + a[p][q] < d[p][q]) {
            d[p][q] = d[i][j] + a[p][q];
            iDex.push({ p, q, d[p][q] });
          }
        }
        
        void right(Node x) {
          int i = x.x, j = x.y, p = x.x, q = x.y + 1;
          if (q <= n && d[i][j] + a[i][j] < d[p][q]) {
            d[p][q] = d[i][j] + a[i][j];
            iDex.push({ p, q, d[p][q] });
          }
        }
        
        void dijkstra() {
          for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
              d[i][j] = INF;
            }
          }
        
          d[m][n] = 0;
        
          iDex.push({ m, n, d[m][n] });
          
          while (!iDex.empty()) {
            Node currentNode = iDex.top();
            iDex.pop();
        
            //cout << currentNode.x << " " << currentNode.y << " " << currentNode.dist << endl;
        
            if (currentNode.x == 0) ans = min(ans, d[currentNode.x][currentNode.y]);
            if (currentNode.dist > d[currentNode.x][currentNode.y] || currentNode.x == 0)
              continue;
            up(currentNode);
            down(currentNode);
            left(currentNode);
            right(currentNode);
          }
        }
        
        int main() {
          cin >> m >> n;
        
          for (int i = 1; i <= m * 2; i++) {
            if (i % 2 == 0) { 
              for (int j = 1; j <= n - 1; j++) cin >> a[(i + 1) / 2][j]; // --> mang luu duong di ngang
            }
            else for (int j = 1; j <= n; j++) cin >> b[((i + 1) / 2)][j]; // --> mang luu duong di len xuong
          }
        
          dijkstra();
        
          cout << ans << endl;
        
          return 0;
        }