Description
泽泽已52:0的比分输了球，被足球流氓打了一顿，扔进了窨井里…… 出来的时候，泽泽已经在埃及了。 滚滚的黄沙在周围飞舞，没有一样生物在这里栖息。泽泽不想就挂在这里。忽然，泽泽被风沙遮住的眼睛瞥见了一座金字塔。这是一座很雄伟的金字塔，而且重要的是，金字塔顶端，竟然有一架直升飞机！ 泽泽就像抓到了救命稻草，用他在长城上999999999999999999 mod 2倍的速度疯狂向金字塔奔跑。来到金字塔下，风把他刮进了金字塔。 门“轰隆隆”地关上了。泽泽看见里面陈列着很多珍品，但依然存在着暗器。但是还好，有个盗墓的把木乃伊给挖走了，所以在金字塔里没有跳动的僵尸。泽泽需要做的就是尽快跑想金字塔的顶端。 现在泽泽在金字塔最底层的左上角。他可以向前后左右或走到楼上去，但必须花费一点时间。一旦走到楼上后楼下的门就会关闭，泽泽不能回下去了，因此泽泽格外小心。幸运的是，金字塔很巧妙。在金字塔里有一些暗道，可以从某点直接通向某点，而不用再走最平常的路线，也是只能上不能下。泽泽知道这些暗道在哪里，而且知道走到每个地方的所花费的时间。 现在你要做的就是算出泽泽走到金字塔顶端所花最少的时间。 注意： 第n层第i行第j列我们表示成n，i，j。当n>=2时，n，i，j可以由4个位置走来（不包括暗道）。如3，1，1可以从2，1，1或2，1，2或2，2，1或2，2，2走来。 如图所示，一座大小为3的金字塔的俯视图就是这个样子的。从A（2，1，1）、B（2，1，2）、C（2，2，1）、D（2，2，2）都可以走到E（3，1，1）。其他位置依次类推。
Input
第1行为2个整数n，m。n表示金字塔的底部边长以及高，m表示有多少暗道。 接下来有n张正方形的图，每张图用一个回车隔开，表示从最底层到最高层的每个位置所花费的时间。保证上面的图的边长比下面图的多1。（如样例，这座大小为4的金字塔第1层是4*4的，第2层是3*3，第3层是2*2，第4层是1*1。） 接下来的m行，每行7个整数ai1，bi1，ci1，ai2，bi2，ci2，pi。表示 第ai1层的第bi1行第ci1列 到 第ai2层的第bi2行第ci2列 之间有一条时间为pi的暗道。保证ai1
Output
一个整数，即泽泽走到金字塔顶端的最短时间。
Sample Input
4 2
4 1 5 2 4 3 4 7 1 9 2 8 0 3 5 1
2 8 5 9 3 9 1 1 8
7 4 5 2
42
1 1 2 2 3 1 1 1 3 2 2 2 1 7 Sample Output
52 题目提示 流程： 1 泽泽一开始在1，1，1的位置，总时间为0+4=4。 2 从1，1，1走到1，1，2，总时间为4+1=5。 3 走暗道到了2，3，1，总时间为5+1+1=7。 4 从2，3，1走到2，3，2，总时间为7+1=8。 5 再上楼到了3，2，2，总时间为8+2=10。 6 再上楼到了4，1，1，总时间为10+42=52。 Hint
数据范围 对于50%的数据，n<=5 对于100%的数据，n<=100，m<=50，每格的暗道总数不超过10个。
代码如下：
type arr=record a,b,c,p:longint; end; var i,j,k,a1,a2,b1,b2,c1,c2,t,time,n,m:longint; l:array[0..100,0..100,0..100,0..10]of arr; a,f,s:array[0..100,0..100,0..100]of longint; procedure init; begin readln(n,m); for i:=n downto 1 do for j:=1 to i do begin for k:=1 to i do read(a[i,j,k]); readln; end; for i:=1 to m do begin readln(a1,b1,c1,a2,b2,c2,time); a1:=n+1-a1; a2:=n+1-a2; inc(s[a2,b2,c2]); l[a2,b2,c2,s[a2,b2,c2]].a:=a1; l[a2,b2,c2,s[a2,b2,c2]].b:=b1; l[a2,b2,c2,s[a2,b2,c2]].c:=c1; l[a2,b2,c2,s[a2,b2,c2]].p:=time; end; for i:=2 to n do for j:=0 to i+1 do for k:=0 to i+1 do f[i,j,k]:=99999999; end; procedure sos(i,j,k:longint); begin if f[i,j,k-1]<99999999 then if f[i,j,k-1]>f[i,j,k]+a[i,j,k-1] then begin f[i,j,k-1]:=f[i,j,k]+a[i,j,k-1]; sos(i,j,k-1); end; if f[i,j-1,k]<99999999 then if f[i,j-1,k]>f[i,j,k]+a[i,j-1,k] then begin f[i,j-1,k]:=f[i,j,k]+a[i,j-1,k]; sos(i,j-1,k); end; if f[i,j,k+1]<99999999 then if f[i,j,k+1]>f[i,j,k]+a[i,j,k+1] then begin f[i,j,k+1]:=f[i,j,k]+a[i,j,k+1]; sos(i,j,k+1); end; if f[i,j+1,k]<99999999 then if f[i,j+1,k]>f[i,j,k]+a[i,j+1,k] then begin f[i,j+1,k]:=f[i,j,k]+a[i,j+1,k]; sos(i,j+1,k); end; end; function min(a,b:longint):longint; begin if a>b then exit(b) else exit(a); end; procedure main; begin f[n,1,1]:=a[n,1,1]; for j:=1 to n do for k:=1 to n do f[n,j,k]:=min(f[n,j,k],min(f[n,j-1,k],f[n,j,k-1])+a[n,j,k]); sos(n,j,k); for i:=n-1 downto 1 do begin for j:=1 to i do for k:=1 to i do begin a1:=min(f[i+1,j,k],f[i+1,j,k+1]); a2:=min(f[i+1,j+1,k],f[i+1,j+1,k+1]); f[i,j,k]:=min(a1,a2)+a[i,j,k]; for t:=1 to s[i,j,k] do begin a1:=l[i,j,k,t].a; b1:=l[i,j,k,t].b; c1:=l[i,j,k,t].c; time:=l[i,j,k,t].p; if f[a1,b1,c1]+time+a[i,j,k]<f[i,j,k] then f[i,j,k]:=f[a1,b1,c1]+time+a[i,j,k]; end; end; for j:=1 to i do for k:=1 to i do sos(i,j,k); end; end; begin init; main; writeln(f[1,1,1]); end.