题面
思路
要求删去最少边权和，使得左上角与右下角不连通，即最小割的模型，但数据规模(500^2)无法使用
如果我们假设左上角向左上画一条无限延伸的线，右下角向右下画一条无限延伸的线
那么可以将图中的边看作点，图中的连通区域看作边，题目也就转化成了寻找从右上区域走到左下区域的最短路
至此就理论AC了，接下来就是码力问题，处理好三种不同的边之间的关系即可（下面的代码写得很麻烦，但大部分也算是复制粘贴，采用SPFA的方法搜索）
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
int n,m;
ll rd[3][1005][1005]; //水平/竖直/斜边
ll dis[3][1005][1005];
bool vis[3][1005][1005];
struct node
{
int d,x,y;
node(){}
node(int _d,int _x,int _y){
d=_d;
x=_x;
y=_y;
}
};
void solve()
{
rep(i,1,n+1)
rep(j,1,m)
{
cin>>rd[0][i][j];
dis[0][i][j]=LINF;
}
rep(i,1,n)
rep(j,1,m+1)
{
cin>>rd[1][i][j];
dis[1][i][j]=LINF;
}
rep(i,1,n*2)
rep(j,1,m*2)
{
cin>>rd[2][i][j];
dis[2][i][j]=LINF;
}
queue<node> q;
rep(j,1,m)
{
q.push(node(0,1,j));
dis[0][1][j]=rd[0][1][j];
}
rep(i,1,n)
{
q.push(node(1,i,m+1));
dis[1][i][m+1]=rd[1][i][m+1];
}
while(!q.empty())
{
node nd=q.front();
q.pop();
int &x=nd.x,&y=nd.y,px,py;
vis[nd.d][x][y]=false;
if(nd.d==0)
{
if(x!=1)
{
px=x*2-2,py=y*2-1;
if(dis[2][px][py]>dis[0][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[0][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x*2-2,py=y*2;
if(dis[2][px][py]>dis[0][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[0][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
}
if(x!=n+1)
{
px=x*2-1,py=y*2-1;
if(dis[2][px][py]>dis[0][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[0][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x*2-1,py=y*2;
if(dis[2][px][py]>dis[0][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[0][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
}
}
else if(nd.d==1)
{
if(y!=1)
{
px=x*2-1,py=y*2-2;
if(dis[2][px][py]>dis[1][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[1][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x*2,py=y*2-2;
if(dis[2][px][py]>dis[1][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[1][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
}
if(y!=m+1)
{
px=x*2-1,py=y*2-1;
if(dis[2][px][py]>dis[1][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[1][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x*2,py=y*2-1;
if(dis[2][px][py]>dis[1][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[1][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
}
}
else
{
if(x&1)
{
if(y&1)
{
px=x,py=y+1;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x+1,py=y;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=(x+1)/2,py=(y+1)/2;
if(dis[0][px][py]>dis[2][x][y]+rd[0][px][py])
{
dis[0][px][py]=dis[2][x][y]+rd[0][px][py];
if(!vis[0][px][py])
{
vis[0][px][py]=true;
q.push(node(0,px,py));
}
}
px=(x+1)/2,py=(y+1)/2;
if(dis[1][px][py]>dis[2][x][y]+rd[1][px][py])
{
dis[1][px][py]=dis[2][x][y]+rd[1][px][py];
if(!vis[1][px][py])
{
vis[1][px][py]=true;
q.push(node(1,px,py));
}
}
}
else
{
px=x,py=y-1;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x+1,py=y;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=(x+1)/2,py=(y+1)/2;
if(dis[0][px][py]>dis[2][x][y]+rd[0][px][py])
{
dis[0][px][py]=dis[2][x][y]+rd[0][px][py];
if(!vis[0][px][py])
{
vis[0][px][py]=true;
q.push(node(0,px,py));
}
}
px=(x+1)/2,py=(y+2)/2;
if(dis[1][px][py]>dis[2][x][y]+rd[1][px][py])
{
dis[1][px][py]=dis[2][x][y]+rd[1][px][py];
if(!vis[1][px][py])
{
vis[1][px][py]=true;
q.push(node(1,px,py));
}
}
}
}
else
{
if(y&1)
{
px=x,py=y+1;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x-1,py=y;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=(x+1)/2,py=(y+1)/2;
if(dis[1][px][py]>dis[2][x][y]+rd[1][px][py])
{
dis[1][px][py]=dis[2][x][y]+rd[1][px][py];
if(!vis[1][px][py])
{
vis[1][px][py]=true;
q.push(node(1,px,py));
}
}
px=(x+2)/2,py=(y+1)/2;
if(dis[0][px][py]>dis[2][x][y]+rd[0][px][py])
{
dis[0][px][py]=dis[2][x][y]+rd[0][px][py];
if(!vis[0][px][py])
{
vis[0][px][py]=true;
q.push(node(0,px,py));
}
}
}
else
{
px=x,py=y-1;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=x-1,py=y;
if(dis[2][px][py]>dis[2][x][y]+rd[2][px][py])
{
dis[2][px][py]=dis[2][x][y]+rd[2][px][py];
if(!vis[2][px][py])
{
vis[2][px][py]=true;
q.push(node(2,px,py));
}
}
px=(x+1)/2,py=(y+2)/2;
if(dis[1][px][py]>dis[2][x][y]+rd[1][px][py])
{
dis[1][px][py]=dis[2][x][y]+rd[1][px][py];
if(!vis[1][px][py])
{
vis[1][px][py]=true;
q.push(node(1,px,py));
}
}
px=(x+2)/2,py=(y+1)/2;
if(dis[0][px][py]>dis[2][x][y]+rd[0][px][py])
{
dis[0][px][py]=dis[2][x][y]+rd[0][px][py];
if(!vis[0][px][py])
{
vis[0][px][py]=true;
q.push(node(0,px,py));
}
}
}
}
}
}
ll ans=LINF;
rep(j,1,m)
ans=min(ans,dis[0][n+1][j]);
rep(i,1,n)
ans=min(ans,dis[1][i][1]);
cout<<ans<<'
';
}
int main()
{
closeSync;
while(cin>>n>>m)
{
solve();
}
return 0;
}