【CEOI2014】bzoj4356 Wall 题解

先粘代码…… ```C #include<cstdio> #include<queue> #include<algorithm> using namespace std;const int N=410; bool mrk[N][N][4];int n;int m;typedef long long ll; struct data{ll d;int v;friend bool operator <(data a,data b){return a.d>b.d;}}; priority_queue <data> pq;int tr[N][N];int xrt[N*N];int yrt[N*N];bool imp[N*N]; int tr1[N][N][4]; inline void delx(int y1,int y2,const int& x) {if(y1>y2)swap(y1,y2);mrk[x][y1][3]=true,mrk[x][y2][1]=true;} inline void dely(int x1,int x2,const int& y) {if(x1>x2)swap(x1,x2);mrk[x1][y][2]=true,mrk[x2][y][0]=true;} namespace G1 { const int N=410*410;const int E=10*N;int v[E];int x[E];int ct;int al[N];ll val[E];int ctt; struct dis{int fr;ll d;}d[N];bool book[N]; inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} inline void dijkstra(int s) { for(int i=1;i<=ctt;i++)d[i].d=0x3f3f3f3f;d[s].d=0;pq.push((data){0,s}); while(!pq.empty()) { data nw=pq.top();pq.pop();if(book[nw.v])continue;book[nw.v]=true; for(int i=al[nw.v];i;i=x[i]) if(!book[v[i]]&&d[v[i]].d>nw.d+val[i]) d[v[i]]=(dis){nw.v,nw.d+val[i]},pq.push((data){d[v[i]].d,v[i]}); } //for(int i=1;i<=ctt;i++)printf("(%d,%d)->(%d,%d) [%lld]\n",xrt[i],yrt[i],xrt[d[i].fr],yrt[d[i].fr],d[i].d); } inline void tmrk() { for(int i=1;i<=ctt;i++) if(imp[i])for(int p=i;d[p].fr;p=d[p].fr) { int u=p;int v=d[p].fr; if(xrt[u]==xrt[v])delx(yrt[u],yrt[v],xrt[u]);else dely(xrt[u],xrt[v],yrt[u]); } } } namespace G2 { const int N=4*410*410;const int E=10*N;int v[E];int x[E];int ct;int al[N]; ll d[N];bool book[N];ll val[E];int ctt; inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} inline ll dijkstra(int s,int t) { for(int i=1;i<=ctt;i++)d[i]=0x3f3f3f3f;d[s]=0;pq.push((data){0,s}); while(!pq.empty()) { data nw=pq.top();pq.pop();if(book[nw.v])continue;book[nw.v]=true; for(int i=al[nw.v];i;i=x[i]) if(!book[v[i]]&&d[v[i]]>nw.d+val[i]) {d[v[i]]=nw.d+val[i],pq.push((data){d[v[i]],v[i]});} }return d[t]; } } int main() { scanf("%d%d",&n,&m);n++;m++; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)tr[i][j]=++G1::ctt,xrt[G1::ctt]=i,yrt[G1::ctt]=j; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<4;k++)tr1[i][j][k]=++G2::ctt; for(int i=1;i<n;i++) for(int j=1,t;j<m;j++) { scanf("%d",&t);if(t)imp[tr[i][j]]=true; if(t){dely(i,i+1,j);dely(i,i+1,j+1);delx(j,j+1,i);delx(j,j+1,i+1);} } for(int i=1;i<n;i++) for(int j=1,va;j<=m;j++) { scanf("%d",&va);G1::add(tr[i][j],tr[i+1][j],va);G1::add(tr[i+1][j],tr[i][j],va); G2::add(tr1[i][j][1],tr1[i+1][j][0],va);G2::add(tr1[i+1][j][0],tr1[i][j][1],va); G2::add(tr1[i][j][2],tr1[i+1][j][3],va);G2::add(tr1[i+1][j][3],tr1[i][j][2],va); } for(int i=1;i<=n;i++) for(int j=1,va;j<m;j++) { scanf("%d",&va);G1::add(tr[i][j],tr[i][j+1],va);G1::add(tr[i][j+1],tr[i][j],va); G2::add(tr1[i][j][3],tr1[i][j+1][0],va);G2::add(tr1[i][j+1][0],tr1[i][j][3],va); G2::add(tr1[i][j][2],tr1[i][j+1][1],va);G2::add(tr1[i][j+1][1],tr1[i][j][2],va); }G1::dijkstra(tr[1][1]);G1::tmrk();mrk[1][1][0]=mrk[1][1][1]=mrk[1][1][2]=mrk[1][1][3]=true; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!mrk[i][j][0])G2::add(tr1[i][j][0],tr1[i][j][3],0),G2::add(tr1[i][j][3],tr1[i][j][0],0); if(!mrk[i][j][1])G2::add(tr1[i][j][0],tr1[i][j][1],0),G2::add(tr1[i][j][1],tr1[i][j][0],0); if(!mrk[i][j][2])G2::add(tr1[i][j][1],tr1[i][j][2],0),G2::add(tr1[i][j][2],tr1[i][j][1],0); if(!mrk[i][j][3])G2::add(tr1[i][j][2],tr1[i][j][3],0),G2::add(tr1[i][j][3],tr1[i][j][2],0); } printf("%lld",G2::dijkstra(tr1[1][1][3],tr1[1][1][1]));return 0; } ```