思维好题。
- 找到结论，即包住所有点的充要条件
两次最短路的思想确实很妙。
结论：找到 \((0,0)\) 到每个标记方格左上角的最短路，那么一定存在包住这些路径的最优解。
证明考虑反证，比较好证的。
代码
#include<bits/stdc++.h>
#define id(i,j) ((i)*(m+1)+(j))
using namespace std;
using ll=long long;
const int N=4e2+10,V=N*N,M=V*4;
int n,m,a[N][N];
vector<pair<int,int> >A[V],B[M];
void add(vector<pair<int,int> >*A,int u,int v,int w){
// if(*A==*::A)fprintf(stderr,"%d %d %d\n",u,v,w);
// else fprintf(stderr,"\t%d %d %d\n",u,v,w);
A[u].push_back({v,w});
A[v].push_back({u,w});
}
int vis[M],pre[V];
ll f[V],g[M];
#define v e.first
#define w e.second
void dij1(){
memset(f,0x3f,sizeof f);
priority_queue<pair<ll,int> >q;
q.push({f[0]=0,0});
for(int u;!q.empty();){
u=q.top().second,q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto e:A[u])if(f[v]>f[u]+w)
f[v]=f[u]+w,pre[v]=u,q.push({-f[v],v});
}
}
ll dij2(int s,int t){
memset(vis,0,sizeof vis);
memset(g,0x3f,sizeof g);
priority_queue<pair<ll,int> >q;
q.push({g[s]=0,s});
for(int u;!q.empty();){
u=q.top().second,q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto e:B[u])if(g[v]>g[u]+w)
g[v]=g[u]+w,q.push({-g[v],v});
}
return g[t];
}
#undef v
#undef w
int p[N][N],q[N][N];
int k,R[V],D[V],idx[V][4];
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&a[i][j]);
for(int i=0;i<n;i++)for(int j=0;j<=m;j++)
scanf("%d",&q[i][j]),add(A,id(i,j),id(i+1,j),q[i][j]);
for(int i=0;i<=n;i++)for(int j=0;j<m;j++)
scanf("%d",&p[i][j]),add(A,id(i,j),id(i,j+1),p[i][j]);
dij1();
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(a[i][j]){
R[id(i,j)]=R[id(i+1,j)]=D[id(i,j)]=D[id(i,j+1)]=1;
for(int u=id(i,j);u;u=pre[u]){
if(abs(u-pre[u])==1)R[min(u,pre[u])]=1;
else if(abs(u-pre[u])==m+1)D[min(u,pre[u])]=1;
else assert(0);
}
}
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
for(int x=0;x<4;x++)idx[id(i,j)][x]=++k;
if(!i&&!j)continue;
int t[4];
copy(idx[id(i,j)],idx[id(i,j)]+4,t);
if(!i||!D[id(i-1,j)])add(B,t[0],t[1],0);
if(!j||!R[id(i,j-1)])add(B,t[0],t[3],0);
if(i>n||!D[id(i,j)])add(B,t[2],t[3],0);
if(j>m||!R[id(i,j)])add(B,t[1],t[2],0);
}
for(int i=0;i<=n;i++)for(int j=0;j<m;j++){
add(B,idx[id(i,j)][1],idx[id(i,j+1)][0],p[i][j]);
add(B,idx[id(i,j)][2],idx[id(i,j+1)][3],p[i][j]);
}
for(int i=0;i<n;i++)for(int j=0;j<=m;j++){
add(B,idx[id(i,j)][3],idx[id(i+1,j)][0],q[i][j]);
add(B,idx[id(i,j)][2],idx[id(i+1,j)][1],q[i][j]);
}
cout<<dij2(idx[id(0,0)][3],idx[id(0,0)][1]);
return 0;
}