#include "wombats.h" #include <iostream> using namespace std; int math[5005][202]; int matv[5005][202]; int aint[10005][202][202]; int spar[205]; int bucket=0,c,r; int inf=50000000; void build(int node,int st,int dr) { if(dr-st<=bucket) { for(int i=1; i<c; i++) { spar[i]=spar[i-1]+math[st][i-1]; } for(int i=0; i<c; i++) { for(int j=0; j<c; j++) { aint[node][i][j]=spar[max(i,j)]-spar[min(i,j)]; } } return; } int mij=(st+dr)/2; build(node*2,st,mij); build(node*2+1,mij+1,dr); for(int i=0; i<c; i++) { for(int j=0; j<c; j++) { aint[node][i][j]=inf; for(int z=0; z<c; z++) { aint[node][i][j]=min(aint[node][i][j],aint[node*2][i][z]+aint[node*2+1][z][j]+matv[mij][z]); } } } } void recalc(int node,int st,int dr,int poz) { if(poz==st && poz==dr) { for(int i=1; i<c; i++) { spar[i]=spar[i-1]+math[st][i-1]; } for(int i=0; i<c; i++) { for(int j=0; j<c; j++) { aint[node][i][j]=spar[max(i,j)]-spar[min(i,j)]; } } return; } if(poz>dr || poz<st) { return; } int mij=(st+dr)/2; recalc(node*2,st,mij,poz); recalc(node*2+1,mij+1,dr,poz); for(int i=0; i<c; i++) { for(int j=0; j<c; j++) { aint[node][i][j]=inf; for(int z=0; z<c; z++) { aint[node][i][j]=min(aint[node][i][j],aint[node*2][i][z]+aint[node*2+1][z][j]+matv[mij][z]); } } } } void init(int R, int C, int H[5000][200], int V[5000][200]) { c=C; r=R; for(int i=0; i<R; i++) { for(int j=0; j<C-1; j++) { math[i][j]=H[i][j]; } } for(int i=0; i<R-1; i++) { for(int j=0; j<C; j++) { matv[i][j]=V[i][j]; } } build(1,0,r-1); } void changeH(int P, int Q, int W) { math[P][Q]=W; recalc(1,0,r-1,P); } void changeV(int P, int Q, int W) { matv[P][Q]=W; recalc(1,0,r-1,P); } int escape(int V1, int V2) { int minim=inf; int mij=(r-1)/2; for(int i=0;i<c;i++) { minim=min(minim,aint[2][V1][i]+aint[3][i][V2]+matv[mij][i]); } return minim; }