传送门

如果只从回路的角度入手的话,很难排除多个独立回路的情况。所以我们考虑通过某种方法把这些城市连接起来。

通过观察(?)可以发现,我们从每个城市的四个点之一走到左上角城市的四个点之一的最短路,一定会被包含在围墙内。否则,我们就可以调整围墙,使其包含这条最短路径,并且总花费不会变高。

这样,我们就可以先预处理出必须被包含在内的边集,这其实等价于我们的围墙不能穿过这些边。我们可以通过拆点建图来限制路径穿过这些边。这样的话,求一条从左上角出发再回到左上角的最短路径就行了。

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 4000010
#define MAXM 410
#define LL long long
using namespace std;

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN];

int n,m;
int g[MAXN],nume;
int tag[MAXM][MAXM],tag1[MAXM][MAXM],tag2[MAXM][MAXM];
int w1[MAXM][MAXM],w2[MAXM][MAXM];
int p[MAXM][MAXM][4],pid[MAXN][3],nump;
bool visit[MAXN];
LL d[MAXN];
int pre[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
    e[nume]=edge(u,g[v],w);
    g[v]=nume++;
}

void dijk(int S){
    static priority_queue< pair<LL,int> > Q;
    memset(d,0x11,sizeof d);
    Q.push(make_pair(0,S));
    d[S]=0;
    while(!Q.empty()){
        pair<LL,int> temp=Q.top();
        Q.pop();
        int x=temp.second;
        if(visit[x]) continue;
        for(int i=g[x];~i;i=e[i].next)
            if(d[x]+e[i].w<d[e[i].to]){
                d[e[i].to]=d[x]+e[i].w;
                pre[e[i].to]=x;
                Q.push(make_pair(-d[e[i].to],e[i].to));
            }
    }
}

void gao2(int x,int y){
    tag1[x][y-1]=1; tag1[x][y]=1;
    tag2[x-1][y]=1; tag2[x][y]=1;
    LL mind=min(min(d[p[x-1][y-1][0]],d[p[x][y-1][0]]),min(d[p[x-1][y][0]],d[p[x][y][0]]));
    if(d[p[x-1][y-1][0]]==mind) x--,y--;
    else if(d[p[x-1][y][0]]==mind) x--;
    else if(d[p[x][y-1][0]]==mind) y--;
    while(x || y){
        int tar=pre[p[x][y][0]];
        int tx=pid[tar][0],ty=pid[tar][1];
        if(tx==x-1) tag1[x][y]=1;
        if(tx==x+1) tag1[x+1][y]=1;
        if(ty==y-1) tag2[x][y]=1;
        if(ty==y+1) tag2[x][y+1]=1;
        x=tx; y=ty;
    }
}

void gao1(){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(int i=0;i<=n;i++) 
        for(int j=0;j<=m;j++){
            p[i][j][0]=++nump;
            pid[nump][0]=i;
            pid[nump][1]=j;
        }
    for(int i=1;i<=n;i++) 
        for(int j=0;j<=m;j++)
            addEdge(p[i-1][j][0],p[i][j][0],w1[i][j]);
    for(int i=0;i<=n;i++) 
        for(int j=1;j<=m;j++)
            addEdge(p[i][j-1][0],p[i][j][0],w2[i][j]);
    addEdge(p[0][0][0],p[0][1][0],0);
    addEdge(p[1][1][0],p[0][1][0],0);
    addEdge(p[1][0][0],p[1][1][0],0);
    addEdge(p[1][0][0],p[0][0][0],0);
    dijk(p[0][0][0]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(tag[i][j])
                gao2(i,j);
}

LL gao3(){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            p[i][j][0]=++nump;
            p[i][j][1]=++nump;
            p[i][j][2]=++nump;
            p[i][j][3]=++nump;
        }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            addEdge(p[i][j][0],p[i-1][j][2],w1[i][j]);
            addEdge(p[i][j][1],p[i-1][j][3],w1[i][j]);
            if(!tag1[i][j]){
                addEdge(p[i][j][0],p[i][j][1],0);
                addEdge(p[i-1][j][2],p[i-1][j][3],0);
            }
        }
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++){
            addEdge(p[i][j][0],p[i][j-1][1],w2[i][j]);
            addEdge(p[i][j][2],p[i][j-1][3],w2[i][j]);
            if(!tag2[i][j]){
                addEdge(p[i][j][0],p[i][j][2],0);
                addEdge(p[i][j-1][1],p[i][j-1][3],0);
            }
        }
    for(int i=1;i<=n;i++) addEdge(p[i][0][0],p[i][0][2],0);
    for(int i=0;i<=n;i++) addEdge(p[i][m][1],p[i][m][3],0);
    for(int j=1;j<=m;j++) addEdge(p[0][j][0],p[0][j][1],0);
    for(int j=0;j<=m;j++) addEdge(p[n][j][2],p[n][j][3],0);
    dijk(p[0][0][2]);
    return d[p[0][0][1]];
}

int main(){
#ifdef DEBUG
    freopen("139.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&tag[i][j]);
    for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) scanf("%d",&w1[i][j]);
    for(int i=0;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w2[i][j]);
    gao1();
    printf("%lld\n",gao3());
}