[最短路 杂题] BZOJ 4356 Ceoi2014 Wall
2017-05-06 09:22:36         来源：雯舞

[最短路 杂题] BZOJ 4356 Ceoi2014 Wall。

#include

#include

#include

#include

#include

#define cl(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long ll;

typedef pair abcd;

inline char nc(){

static char buf[100000],*p1=buf,*p2=buf;

}

char c=nc(),b=1;

for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;

for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;

}

const int N=402*402*4+5;

const int M=N*4;

struct edge{

int u,v,w,next;

}G[M];

inline void add(int u,int v,int w,int p){

}

inline void link(int u,int v,int w){

}

#define V G[p].v

const int _N=405;

int n,m;

int a[_N][_N],b[_N][_N],c[_N][_N];

int tot;

ll dis[N]; int pre[N];

priority_queue,greater > Q;

inline void Dij(int S){

for (int i=1;i<=tot;i++) dis[i]=1LL<<60,pre[i]=0;

dis[S]=0; Q.push(abcd(0,S));

while (!Q.empty()){

abcd t=Q.top(); Q.pop();

int u=t.second;

if (dis[u]!=t.first) continue;

if (dis[V]>dis[u]+G[p].w)

pre[V]=u,Q.push(abcd(dis[V]=dis[u]+G[p].w,V));

}

}

#define P(x,y) ((m+1)*((x)-1)+(y))

#define PP(x,y,z) ((P(x,y)-1)*4+z+1)

int vst[N];

int mark[N][4],del[N];

inline void Link(int u,int v,int w){

if (del[u] || del[v]) return;

}

inline void dfs(int u){

if (u==1 || vst[u]) return;

vst[u]=1;

if (pre[u]==u-1) mark[u][3]=mark[pre[u]][1]=1;

if (pre[u]==u+1) mark[u][1]=mark[pre[u]][3]=1;

if (pre[u]==u-m-1) mark[u][0]=mark[pre[u]][2]=1;

if (pre[u]==u+m+1) mark[u][2]=mark[pre[u]][0]=1;

dfs(pre[u]);

}

int main(){

freopen("t.in","r",stdin);

freopen("t.out","w",stdout);

tot=(n+1)*(m+1);

for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) read(a[i][j]);

Dij(1);

for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]) dfs(P(i,j));

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

if (a[i][j])

del[PP(i,j,2)]=del[PP(i+1,j,1)]=del[PP(i,j+1,3)]=del[PP(i+1,j+1,0)]=1;

del[1]=1;

for (int i=1;i<=n+1;i++)

for (int j=1;j<=m+1;j++)

for (int k=0;k<4;k++)

if (!mark[P(i,j)][k])

for (int i=1;i<=n;i++)

for (int j=1;j<=m+1;j++)

for (int i=1;i<=n+1;i++)

for (int j=1;j<=m;j++)

tot<<=2; Dij(2);

printf("%lld\n",dis[4]);

/*int t=4;

while (t) printf("%d\n",t),t=pre[t];*/

return 0;

}