95pts,但是WA#3
查看原帖
95pts,但是WA#3
280233
Lee666666楼主2023/11/12 09:53

RT,#3是最小规模了,本地按这个规模拍了两万多组数据都没拍出错来,求调qwq
拆点做法,跑spfa

#include <cstdio>
#include <bitset>
#include <queue>
using namespace std;

typedef long long LL;

const int inf = 0x3f3f3f3f;

inline int read() {
	int s = 0;
	char ch = getchar();
	while (ch < 48 || ch > 57) {
		ch = getchar();
	}
	while (ch > 47 && ch < 58) {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}

inline int min(int a, int b) {
	return a < b ? a : b;
}

inline int max(int a, int b) {
	return a > b ? a : b;
}

bitset<6750015> inq;
int n, m, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, a[155][155], b[155][155], dis[6750015];
queue<int> q; 

inline int turn(int x, int y, int z) {
	return x * m * (n + m - 1) + y * (n + m - 1) + z;
}

void spfa(int s) {
	for (int i = 0; i < n * m * (n + m - 1); i++) {
		dis[i] = inf;
	}
	dis[s] = 0;
	inq.set(s, 1);
	q.push(s);
	int u, v, x, y, z, tx, ty;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		inq.set(u, 0);
		z = u % (n + m - 1);
		y = u / (n + m - 1) % m;
		x = u / (n + m - 1) / m;
		if (z) {
			for (int i = 0; i < 4; i++) {
				tx = x + dir[i][0];
				ty = y + dir[i][1];
				if (~tx && tx < n && ~ty && ty < m) {
					v = turn(tx, ty, z - 1);
						if (dis[u] < dis[v]) {
						dis[v] = dis[u];
						if (!inq.test(v)) {
							q.push(v);
							inq.set(v, 1);
						}
					}
				}
			}
			v = turn(x, y, z - 1);
			if (dis[u] < dis[v]) {
				dis[v] = dis[u];
				if (!inq.test(v)) {
					q.push(v);
					inq.set(v, 1);
				}
			}
		}
		if (z < b[x][y]) {
			v = turn(x, y, b[x][y]);
			if (dis[u] + a[x][y] < dis[v]) {
				dis[v] = dis[u] + a[x][y];
				if (!inq.test(v)) {
					q.push(v);
					inq.set(v, 1);
				}
			}
		}
	}
	return;
}

int main() {
	n = read();
	m = read(); 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b[i][j] = min(read(), max(i, n - i - 1) + max(j, n - j - 1));
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = read();
		}
	}
	int x1, y1, x2, y2, x3, y3, dis12, dis13, dis21, dis23, dis31, dis32;
	x1 = read() - 1;
	y1 = read() - 1;
	x2 = read() - 1;
	y2 = read() - 1;
	x3 = read() - 1;
	y3 = read() - 1;
	spfa(turn(x1, y1, 0));
	dis12 = dis[turn(x2, y2, 0)];
	dis13 = dis[turn(x3, y3, 0)];
	spfa(turn(x2, y2, 0));
	dis21 = dis[turn(x1, y1, 0)];
	dis23 = dis[turn(x3, y3, 0)];
	spfa(turn(x3, y3, 0));
	dis31 = dis[turn(x1, y1, 0)];
	dis32 = dis[turn(x2, y2, 0)];
	char ch;
	int ans = inf;
	if (dis21 + dis31 < ans) {
		ans = dis21 + dis31;
		ch = 'X';
	}
	if (dis12 + dis32 < ans) {
		ans = dis12 + dis32;
		ch = 'Y';
	}
	if (dis13 + dis23 < ans) {
		ans = dis13 + dis23;
		ch = 'Z';
	}
	if (ans == inf) {
		printf("NO\n");
	}
	else {
		printf("%c\n%d\n", ch, ans);
	}
	return 0;
}
2023/11/12 09:53
加载中...