题目链接

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5, K = 25;

int n, m, k, Q, R, f[N], fa[N], cnt, tot;

int D(int x, int y, int w) {
	return ((x - 1) * m * k) + ((y - 1) * k) + w;
}

vector<int> v[N];

struct S {
	int x, y, w;
} a[N * 3];

struct CNT {
	int x, y, w, sx;
};

queue<CNT> q;

int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

void Bfs() {
	for (; !q.empty(); q.pop()) {
		CNT cur = q.front();
		for (int i = 0; i < 6; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			int nw = cur.w + dz[i];
			int nxt = D(nx, ny, nw);
			if (nx < 1 || nx > n || ny < 1 || ny > m || nw < 1 || nw > k || f[nxt] <= (int)1e7) {
				continue;
			}
			f[nxt] = f[cur.sx] + 1;
			q.push({nx, ny, nw, nxt});
		}  
	}
}

bool cmp(S X, S Y) {
	return X.w > Y.w;
} 

int find(int x) {
	return (x == fa[x] ? x : fa[x] = find(fa[x]));
}

struct A {
	int f[K], dp[K], o;
} s[N];

void Dfs(int x, int fa) {
	s[x].f[0] = fa;
	s[x].dp[0] = min(f[x], f[fa]);
	s[x].o = s[fa].o + 1;
	for (int nx : v[x]) {
		if (nx == fa) {
			continue;
		}
		Dfs(nx, x);
	}
}

void init() {
	for (int j = 1; j <= 23; j++) {
		for (int i = 1; i <= n; i++) {
			s[i].f[j] = s[s[i].f[j - 1]].f[j - 1];
			s[i].dp[j] = min(s[i].dp[j - 1], s[s[i].f[j - 1]].dp[j - 1]);
		}
	}
}

int LCA(int x, int y) {
	if (s[x].o < s[y].o) {
		swap(x, y);
	}
	int ans = min(f[x], f[y]);
	for (int j = 23; j >= 0; j--) {
		if (s[s[x].f[j]].o >= s[y].o) {
			ans = min(ans, s[x].dp[j]);
			x = s[x].f[j];
		}
	}
	for (int j = 23; j >= 0; j--) {
		if (s[x].f[j] != s[y].f[j]) {
			ans = min(ans, s[x].dp[j]);
			ans = min(ans, s[y].dp[j]);
			x = s[x].f[j];
			y = s[y].f[j];
		}
	}
	if (x != y) {
		ans = min(ans, s[x].dp[0]);
		ans = min(ans, s[y].dp[0]);
		x = s[x].f[0];
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k >> R;
	memset(f, 0x3f, sizeof(f)); 
	for (int i = 1, x, y, w; i <= R; i++) {
		cin >> x >> y >> w;
		int sx = D(x, y, w);
		f[sx] = 0;
		q.push({x, y, w, sx});
	}
	Bfs();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int e = 1; e < k; e++) {
				int x = D(i, j, e), y = D(i, j, e + 1);
				a[++tot] = {x, y, min(f[x], f[y])};
			}
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int e = 1; e <= k; e++) {
				int x = D(i, j, e), y = D(i + 1, j, e);
				a[++tot] = {x, y, min(f[x], f[y])};
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < m; j++) {
			for (int e = 1; e <= k; e++) {
				int x = D(i, j, e), y = D(i, j + 1, e);
				a[++tot] = {x, y, min(f[x], f[y])};
			}
		}
	}
	sort (a + 1, a + 1 + tot, cmp);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int e = 1; e <= k; e++) {
				int x = D(i, j, e);
				fa[x] = x;
			}
		}
	}
	cnt = n * m * k;
	for (int i = 1; i <= tot; i++) {
		int x = a[i].x, y = a[i].y, w = a[i].w;
		if (find(x) == find(y)) {
			continue;
		} 
		cnt++;
		f[cnt] = w;
		fa[cnt] = cnt;
		x = find(x), y = find(y);
		v[x].push_back(cnt), v[cnt].push_back(x);
		v[y].push_back(cnt), v[cnt].push_back(y);
		fa[x] = cnt, fa[y] = cnt;
	}
	Dfs(cnt, 0), init();
	cin >> Q;
	for (int sx, sy, sw, ex, ey, ew; Q--;) {
		cin >> sx >> sy >> sw;
		cin >> ex >> ey >> ew;
		int x = D(sx, sy, sw), y = D(ex, ey, ew);
		if (x == y) {
			cout << f[x] << "\n";
			continue;
		}
		cout << min(f[x], min(f[y], LCA(x, y))) << "\n";
	}
	return 0;
}