题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2007

题解：

网络流、最小割、对偶图

奇妙的题 ~

种种原因导致了高度要么为 0，要么为 1 (1),然后 0,1区域是分离的 (2)。
对于 (2) 是显然的，因为如果在一片 1的区域中出现了一个 0，那么把 0改为 1一定会更优。
而对于 (1) ，就只有感性一点理解了（没看到一个比较理性的讲解）。
    由于左上角为 0，右下角为 1，所以总会存在有上坡路。
    那么为了使上坡导致的体力消耗最少，我们会去选择一条流量小(流量设为w)的路从 0直接爬向 1，
    这样才是最优的。
    如果此时不一次性爬上去，而是爬部分高度 h (0<h<1) 那么以后也必然会爬到 1，
    但那时流量的大小就不如之前的 w小了，所以总的消耗是大于在流量小的边一次性爬上 1的。

所以至此，求出左上角 S ->右下角 T 的最小割便是答案了。
（这条割把图分为了 0部 和 1部）

但是跑网络流会超时。
由于图的特殊性——非常规则，
所以就把中间的各个区域抽象成一个个的点，
图的左下的空白区域看成是 S点，
图的右上的空白区域看成是 T点，
然后按照（"左手定则"，诶呀，管的怎么建的，符合题意就可以了）一定的方向把原图的边变为与它垂直的边（边权不变），连接新的那些点，
最后跑一个更加高效的最短路算法，求出S->T的最短路就是答案了。
（可以感性理解为是在模拟去割那张图）。

代码：

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 300000

#define MAXM 3000000

#define ll long long

using namespace std;

struct Edge{

	ll to[MAXM],val[MAXM],nxt[MAXM],head[MAXN],ent;

	void Init(){ent=2;}//记得初始化

	void Adde(ll u,ll v,ll w){

		to[ent]=v; val[ent]=w; nxt[ent]=head[u]; head[u]=ent++;

	}

	ll Next(ll i,bool type){

		return type?head[i]:nxt[i];

	}

}E;

ll dis[MAXN];

ll N;

ll idx(ll i,ll j){

	return (i-1)*N+j;

}

ll Dijkstra(ll S,ll T){

	typedef pair<ll,ll>pii;

	static bool vis[MAXN];

	memset(vis,0,sizeof(vis));

	memset(dis,0x3f,sizeof(dis)); ll u,v;

	priority_queue<pii,vector<pii>,greater<pii> >q; q.push(make_pair(0,S)); dis[S]=0;

	while(!q.empty()){

		u=q.top().second; q.pop();

		if(vis[u]) continue; vis[u]=1;

		for(ll i=E.Next(u,1);i;i=E.Next(i,0)){

			v=E.to[i];

			if(vis[v])continue;

			if(dis[v]<=dis[u]+E.val[i]) continue;

			dis[v]=dis[u]+E.val[i];

			q.push(make_pair(dis[v],v));

		}

	}

	return dis[T];

}

int main()

{

	freopen("altitude.in","r",stdin);freopen("altitude.out","w",stdout);

	E.Init(); ll S,T;

	scanf("%lld",&N);

	S=N*N+1; T=S+1;

	for(ll i=1,x,from,to;i<=N+1;i++)

		for(ll j=1;j<=N;j++){

			scanf("%lld",&x);

			from=i==N+1?S:idx(i,j);

			to=i==1?T:idx(i-1,j);

			E.Adde(from,to,x);

		}

	for(ll i=1,x,from,to;i<=N;i++)

		for(ll j=1;j<=N+1;j++){

			scanf("%lld",&x);

			from=j==1?S:idx(i,j-1);

			to=j==N+1?T:idx(i,j);

			E.Adde(from,to,x);

		}

	for(ll i=1,x,from,to;i<=N+1;i++)

		for(ll j=1;j<=N;j++){

			scanf("%lld",&x);

			from=i==1?T:idx(i-1,j);

			to=i==N+1?S:idx(i,j);

			E.Adde(from,to,x);

		}

	for(ll i=1,x,from,to;i<=N;i++)

		for(ll j=1;j<=N+1;j++){

			scanf("%lld",&x);

			from=j==N+1?T:idx(i,j);

			to=j==1?S:idx(i,j-1);

			E.Adde(from,to,x);

		}

	ll ans=Dijkstra(S,T);

	printf("%lld",ans);

	return 0;

}