#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr pair<int, int>
#define tri array<int, 3>
const int INF = 1e9 + 7;
vector<vector<vector<int>>> edge;
int r, c;
int x[3] = {-1, 0, 1}, y[3] = {0, 1, 0};
bool ok(int i, int j, int t) {
i += x[t]; j += y[t];
if (i < 0 || j < 0 || i >= r || j >= c) return 0;
else return 1;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R; c = C;
edge.resize(R, vector<vector<int>>(C, vector<int>(3, INF)));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (j > 0)
edge[i][j][0] = H[i][j-1];
edge[i][j][1] = V[i][j];
edge[i][j][2] = H[i][j];
}
}
}
void changeH(int P, int Q, int W) {
edge[P][Q][0] = W;
if (Q + 1 < c)
edge[P][Q][2] = W;
}
void changeV(int P, int Q, int W) {
edge[P][Q][1] = W;
}
int escape(int V1, int V2) {
priority_queue<tri, vector<tri>, greater<tri>> q;
q.push({0, 0, V1});
vector<vector<int>> d(r, vector<int> (c, INF));
d[0][V1] = 0;
while (!q.empty()) {
auto [dist, i, j] = q.top(); q.pop();
if (d[i][j] > dist) continue;
for (int t = 0; t < 3; t++) {
if (ok(i, j, t)) {
int te = dist + edge[i][j][t];
if (d[i][j] > te) {
q.push({te, i + x[t], j + y[i]});
}
}
}
}
return d[r-1][V2];
}
