#include <bits/stdc++.h> #include "wombats.h" using namespace std; constexpr int inf = 1e9; int n, m; vector<vector<int>> h, v; vector<multiset<pair<int, int>>> g; vector<int> d0, d1; void dijkstra(int s, vector<int> &d) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; d.assign(n * m, inf); vector<bool> vis(n * m); d[s] = 0; q.push({0, s}); while (!q.empty()) { int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [v, w] : g[u]) { if (d[v] > d[u] + w) { d[v] = d[u] + w; q.push({d[v], v}); } } } } void init(int R, int C, int H[5000][200], int V[5000][200]) { n = R; m = C; h.resize(n, vector<int>(m - 1)); v.resize(n - 1, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (j < m - 1) { h[i][j] = H[i][j]; } if (i < n - 1) { v[i][j] = V[i][j]; } } } g.resize(n * m); for (int i = 0; i < n; i++) { for (int j = 0; j < m - 1; j++) { int k = i * m + j; g[k].insert({k + 1, h[i][j]}); g[k + 1].insert({k, h[i][j]}); } } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { int k = i * m + j; g[k].insert({k + m, v[i][j]}); } } } bool upd = 1; void changeH(int i, int j, int w) { upd = 1; int k = i * m + j; g[k + 1].erase(g[k + 1].find({k, h[i][j]})); g[k].erase(g[k].find({k + 1, h[i][j]})); h[i][j] = w; g[k].insert({k + 1, h[i][j]}); g[k + 1].insert({k, h[i][j]}); } void changeV(int i, int j, int w) { upd = 1; int k = i * m + j; g[k].erase(g[k].find({k + m, v[i][j]})); v[i][j] = w; g[k].insert({k + m, v[i][j]}); } int escape(int s, int t) { if (upd) { dijkstra(0, d0); dijkstra(1, d1); upd = 0; } t += (n - 1) * m; if (s == 0) { return d0[t]; } else { return d1[t]; } }