首先有个结论，筑的墙一定会把 到所有别的关键点的左上角的最短路都围进去。例如：
若当前墙包含的是深蓝色区域，而 到关键点 的左上角的最短路是绿色的线，那么显然把浅蓝色区域也包含进墙里是更优的，因为红色段肯定是比代替它的五小段绿色段的长度和要长的，因为绿色的线是最短路。
为什么是左上角？其实四个角都没关系，这个之后再证明。
求出了 到别的关键点的左上角的最短路之后，问题就转化为最小化筑墙的花费，使得筑出的墙可以圈住所有的最短路和关键点。
那么考虑把一个网格线的交点都拆成四个点，点之间顺时针连边权为 的有向边，属于不同交点的点之间连边权为原权值的有向边，但是要注意经过关键点和最短路的边都不能连：
容易发现，这样建好图之后，从网格左上角的交点拆出来的 号点出发，走到它的 号点，就能筑出合法的墙。那么花费最小的方案显然就是这两点之间的最短路。
最后说一下之前留下来的悬念：
为什么要走到左上角？？？为什么走到哪个角都没关系？？？
不妨先钦定一定从左上角那个关键点的左上角出发，显然走到右上角的最短路一定“围着”走到左上角的最短路，即绿色的线不可能越过红色的线再回来，因为那样不优。
那么分两种情况讨论：
-
走到左上角的最短路是先走到右上角再往左走：
这时由于最后筑的墙要包含所有关键点，所以左上角和右上角之间的那条边不会被筑墙，也就是说，红线和绿线有用的部分是完全相等的，那么自然对答案没有任何影响；
-
走到左上角的最短路不是先走到右上角再往左走：
这时考虑最后跑的最短路，即筑的墙，用紫色的线标识。显然，由于走到左上角的最短路不是先走到右上角再往左走，所以走左上角和右上角的那条边一定是不优的；并且走红线和绿线中间也是不优的，因为红线和绿线是最短路。那么最终的墙只有可能是这样：
所以对最终的答案没有影响；
参考这样的证明方法，容易得出从哪个角出发，走到哪个角都是没有任何关系的。所以为了好写，干脆直接钦定从左上角开始和结束。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int S=5000005,MS=405;
int n,m;
int a[MS][MS];
long long dnval[MS][MS],rgval[MS][MS];
int esum,to[S],nxt[S],h[S];
long long c[S],dis[S];
bool vis[S];
bool dntag[MS][MS],rgtag[MS][MS];
inline int getid(int x,int y)
{
return (x-1)*(m+1)+y;
}
inline int getx(int id)
{
return (id-1)/(m+1)+1;
}
inline int gety(int id)
{
return (id-1)%(m+1)+1;
}
inline void add(int x,int y,long long w)
{
to[++esum]=y;
c[esum]=w;
nxt[esum]=h[x];
h[x]=esum;
}
inline void dijkstra(int s)
{
memset(dis,127,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue<pair<long long,int> > q;
q.push(make_pair(-dis[s],s));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
long long w=c[i];
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
void dfs(int u)
{
vis[u]=true;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
long long w=c[i];
if(dis[u]==dis[v]+w)
{
int ux=getx(u),uy=gety(u),vx=getx(v),vy=gety(v);
if(vx!=ux) dntag[min(ux,vx)][uy]=true;
else rgtag[ux][min(uy,vy)]=true;
if(!vis[v]) dfs(v);
break;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m+1;j++)
{
scanf("%lld",&dnval[i][j]);
int idu=getid(i,j),idv=getid(i+1,j);
add(idu,idv,dnval[i][j]);
add(idv,idu,dnval[i][j]);
}
}
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&rgval[i][j]);
int idu=getid(i,j),idv=getid(i,j+1);
add(idu,idv,rgval[i][j]);
add(idv,idu,rgval[i][j]);
}
}
dijkstra(getid(1,1));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==1&&!vis[getid(i,j)]) dfs(getid(i,j));
esum=0;
memset(h,0,sizeof(h));
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=m+1;j++)
{
int bg=(getid(i,j)-1)*4;
int _0=bg+1,_1=bg+2,_2=bg+3,_3=bg+4;
if(!dntag[i-1][j]&&a[i-1][j-1]==0&&a[i-1][j]==0) add(_0,_1,0);
if(!rgtag[i][j]&&a[i-1][j]==0&&a[i][j]==0) add(_1,_2,0);
if(!dntag[i][j]&&a[i][j]==0&&a[i][j-1]==0) add(_2,_3,0);
if(!rgtag[i][j-1]&&a[i][j-1]==0&&a[i-1][j-1]==0) add(_3,_0,0);
if(i>1)
{
int ubg=(getid(i-1,j)-1)*4;
int u2=ubg+3,u3=ubg+4;
add(u2,_1,dnval[i-1][j]);
add(_0,u3,dnval[i-1][j]);
}
if(j>1)
{
int lbg=(getid(i,j-1)-1)*4;
int l1=lbg+2,l2=lbg+3;
add(l1,_0,rgval[i][j-1]);
add(_3,l2,rgval[i][j-1]);
}
}
}
dijkstra(2);
printf("%lld\n",dis[4]);
return 0;
}