#include<iostream>#include<cstdio>#include<memory.h>#include<vector>#include<queue>using namespace std;#define Clear(f, nr) memset(f, nr, sizeof(f))const int SIZE = 105;const int MSIZE = 400000;const int INF = 1 << 30;struct Node{ int id, cost;};vector<Node> path[MSIZE];int nr[SIZE], beg[SIZE]; int n, m;int move[6][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {-1, -1}, {0, 0}};int C[SIZE][SIZE][SIZE];void Init(int n){ beg[n] = 0; nr[n] = 0; for(int i = n - 1; i >= 0; i --) { nr[i] = (i + 1) * (i + 1); beg[i] = beg[i + 1] + nr[i + 1]; }}void connect(int h, int r, int c, int x){ Node Now; int id = beg[h] + r * (h + 1) + c; for(int i = 0; i < 4; i ++) { int row = r + move[i][0]; int col = c + move[i][1]; if(row >= 0 && col >= 0 && row <= h && col <= h) { Now.id = beg[h] + row * (h + 1) + col; Now.cost = x; path[id].push_back(Now); } } for(int i = 2; i < 6; i ++) { int row = r + move[i][0]; int col = c + move[i][1]; if(row <= h - 1 && col <= h - 1) { if(row >= 0 && col >= 0 && row <= r && col <= c) { Now.id = beg[h - 1] + row * h + col; Now.cost = x; path[id].push_back(Now); } } }}struct Edg{ int id, fee; bool operator<(const Edg& p)const { return p.fee < fee; }};priority_queue<Edg> Q;void Dij(int st, int et){ int d[MSIZE]; for(int i = 0; i <= et; i ++) d[i] = INF; while(!Q.empty()) Q.pop(); Edg Now, tmp; Now.fee = 0, Now.id = st; d[st] = 0; Q.push(Now); while(!Q.empty()) { tmp = Q.top(); Q.pop(); int id = tmp.id; for(int i = 0; i < path[id].size(); i ++) { int v = path[id][i].id, w = path[id][i].cost; if(d[v] > d[id] + w) { d[v] = d[id] + w; Now.fee = d[v]; Now.id = v; Q.push(Now); } } } printf("%dn", d[et] + C[0][0][0]);}int main(){ int x; int x1, y1, z1, x2, y2, z2, co; while(scanf("%d%d", &n, &m) != EOF) { if(n == 0) { puts("0"); continue; } Init(n); for(int i = 0; i <= beg[0]; i ++) path[i].clear(); for(int i = n - 1; i >= 0; i --) { for(int r = 0; r <= i; r ++) { for(int c = 0; c <= i; c ++) { scanf("%d", &x); C[i][r][c] = x; connect(i, r, c, x); } } } Node Now; while(m --) { scanf("%d%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2, &co); x1 = (n - x1), y1 --, z1 --; x2 = (n - x2), y2 --, z2 --; int id1 = beg[x1] + y1 * (x1 + 1) + z1; int id2 = beg[x2] + y2 * (x2 + 1) + z2; Now.cost = C[x1][y1][z1] + co; Now.id = id2; path[id1].push_back(Now); } int st = 0, et = beg[0]; Dij(0, et); }}
