#include "wombats.h" #include <iostream> #include <queue> using namespace std; int math[5005][202]; int matv[5005][202]; int aint[8005][202][202]; int spar[205]; int mat[5001][205]; int bucket=8,c,r; int inf=50000000; void build(int node,int st,int dr) { if(dr-st<=bucket && (dr!=r-1 || st!=0)) { for(int i=0; i<c; i++) { for(int j=st; j<=dr; j++) { for(int z=0; z<c; z++) { mat[j][z]=inf; } } mat[st][i]=0; priority_queue<pair<int,pair<int,int> >>pq; pq.push({-0,{st,i}}); while(pq.size()) { auto curr=pq.top(); pq.pop(); int lin=curr.second.first; int col=curr.second.second; if(-curr.first==mat[lin][col]) { if(lin<dr) { if(mat[lin+1][col]>mat[lin][col]+matv[lin][col]) { mat[lin+1][col]=mat[lin][col]+matv[lin][col]; pq.push({-mat[lin+1][col],{lin+1,col}}); } } if(col+1<c) { if(mat[lin][col+1]>mat[lin][col]+math[lin][col]) { mat[lin][col+1]=mat[lin][col]+math[lin][col]; pq.push({-mat[lin][col+1],{lin,col+1}}); } } if(col>=1) { if(mat[lin][col-1]>mat[lin][col]+math[lin][col-1]) { mat[lin][col-1]=mat[lin][col]+math[lin][col-1]; pq.push({-mat[lin][col-1],{lin,col-1}}); } } } } for(int j=0;j<c;j++) { aint[node][i][j]=mat[dr][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>dr || poz<st) { return; } if(dr-st<=bucket && (dr!=r-1 || st!=0)) { for(int i=0; i<c; i++) { for(int j=st; j<=dr; j++) { for(int z=0; z<c; z++) { mat[j][z]=inf; } } mat[st][i]=0; priority_queue<pair<int,pair<int,int> >>pq; pq.push({-0,{st,i}}); while(pq.size()) { auto curr=pq.top(); pq.pop(); int lin=curr.second.first; int col=curr.second.second; if(-curr.first==mat[lin][col]) { if(lin<dr) { if(mat[lin+1][col]>mat[lin][col]+matv[lin][col]) { mat[lin+1][col]=mat[lin][col]+matv[lin][col]; pq.push({-mat[lin+1][col],{lin+1,col}}); } } if(col+1<c) { if(mat[lin][col+1]>mat[lin][col]+math[lin][col]) { mat[lin][col+1]=mat[lin][col]+math[lin][col]; pq.push({-mat[lin][col+1],{lin,col+1}}); } } if(col>=1) { if(mat[lin][col-1]>mat[lin][col]+math[lin][col-1]) { mat[lin][col-1]=mat[lin][col]+math[lin][col-1]; pq.push({-mat[lin][col-1],{lin,col-1}}); } } } } for(int j=0;j<c;j++) { aint[node][i][j]=mat[dr][j]; } } 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; }