#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][2] = W; if (Q + 1 < c) edge[P][Q+1][0] = 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]; }