首先不难发现海拔高度只能为0或1
因为决策是单调的
不难发现最优决策一定是划分为海拔为0和1两块，不会出现01相间的情况
所以这很明显是一个最小割
由于n*n很大，我们必须要用平面图最小割转化为最短路径
在我们做1001时，是平面无向图，这里是平面有向图，其实是一样的
只要记住以起点终点为对角线划分外面为两个面，然后以面为点，边两侧面连边
最后注意新图的任意一条路径对应原图的一个割即可
最后答案就是最短路
type node=record
loc,num:longint;
end;
cmp=record
point,next,cost:longint;
end; var edge:array[..] of cmp;
heap:array[..] of node;
p,d,where:array[..] of longint;
t,m,n,i,j,k,x,y,len:longint; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].cost:=z;
edge[len].next:=p[x];
p[x]:=len;
end; procedure up(i:longint);
var j,x,y:longint;
begin
j:=i shr ;
while j> do
begin
if heap[i].num<heap[j].num then
begin
x:=heap[i].loc;
y:=heap[j].loc;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=i shr ;
end
else break;
end;
end; procedure sift(i:longint);
var j,x,y:longint;
begin
j:=i shl ;
while j<=m do
begin
if (j<m) and (heap[j].num>heap[j+].num) then inc(j);
if heap[i].num>heap[j].num then
begin
x:=heap[i].loc;
y:=heap[j].loc;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=i shl ;
end
else break;
end;
end; begin
readln(n);
fillchar(p,sizeof(p),);
t:=n*n+;
for i:= to n do
begin
readln(x);
add(,i+,x);
end;
for i:= to n do
for j:= to n do
begin
readln(x);
if i=n then y:=t
else y:=i*n+j+;
add((i-)*n+j+,y,x);
end; for i:= to n do
begin
readln(x);
add((i-)*n+,t,x);
for j:= to n do
begin
readln(x);
add((i-)*n+j+,(i-)*n+j,x);
end;
readln(x);
add(,i*n+,x);
end; for i:= to n do
begin
readln(x);
add(i+,,x);
end;
for i:= to n do
for j:= to n do
begin
readln(x);
if i=n then y:=t
else y:=i*n+j+;
add(y,(i-)*n+j+,x);
end; for i:= to n do
begin
readln(x);
add(t,(i-)*n+,x);
for j:= to n do
begin
readln(x);
add((i-)*n+j,(i-)*n+j+,x);
end;
readln(x);
add(i*n+,,x);
end;
m:=t;
for i:= to t do
begin
if i= then d[i]:=
else d[i]:=;
heap[i].loc:=i;
heap[i].num:=d[i];
where[i]:=i;
end;
for i:= to t do
begin
k:=heap[].loc;
if k=t then break;
x:=heap[m].loc;
where[x]:=;
swap(heap[],heap[m]);
dec(m);
sift();
j:=p[k];
while j<>- do
begin
y:=edge[j].point;
if d[y]>edge[j].cost+d[k] then
begin
d[y]:=edge[j].cost+d[k];
heap[where[y]].num:=d[y];
up(where[y]);
end;
j:=edge[j].next;
end;
end;
writeln(d[t]);
end.