AT_zone2021_e 题解

AT_zone2021_e

题意

由于洛谷的题意太不好理解了，我是看了英文题面才理解的。下面简述一下题意：

首先题目给定两个数 \(R\) 和 \(C\) ，同时给定两个数组 \(A\) 和 \(B\)，\(A\) 的大小是 \(R \times C - 1\) ，\(B\) 的大小是 \(R - 1 \times C\) 。然后计算点 \((1,\, 1)\) 到点 \((R,\, C)\) 的最短路径。

其中，假定当前的点为 \((i, \, j)\) ，那么有几种移动的方式：

  • 移动到 \((i,\, j+1)\)，花费为 \(A_{i,\,j}\)。需要保证 \(j<C\)。

  • 移动到 \((i,\, j-1)\)，花费为 \(A_{i,\,j-1}\)。需要保证 \(j\ge 2\)。

  • 移动到 \((i+1,\, j)\)，花费为 \(B_{i,\,j}\)。需要保证 \(i<R\)。

  • 选择一个整数 \(k\) 满足 \(1\le k<i\)，移动到 \((i-k,\,j)\)，花费为 \((1+k)\)。

思路

第一版

我的第一版思路较为简单。首先我们看一下题目，会发现与 Dijkstra 最短路算法很相似我们直接尝试使用类似 Dijkstra 的算法。我们使用广搜，加上优先队列优化，可以写出时间复杂度较为优秀的算法。

具体实现方法

初始化一个数组 \(dis\) 为极大值，用于保存点 \((1, \, 1)\) 到其余点的最短路径长度。初始化一个优先队列，用于存储节点，注意让长度短的节点处于堆顶。然后进入循环，截止条件为优先队列为空。对于每次循环，取出堆顶，然后按照题目给定的四种移动方式进行松弛操作，逐步的使 \(dis\) 数组收敛到最小值，返回即可。

但是当你打出来的时候，你会发现似乎第四种移动方法会运行的比较慢。不管了，直接交！交完了你会发现实际上这个算法还是比较优秀的，只 TLE 了一个点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <queue>
#include <cstring>

//#define int long long

using namespace std;

bool vis[509][509];
int r, c, a[509][509], b[509][509], dis[509][509];
priority_queue<pair<int, pair<int, int> > > pq;

void bfs(int x, int y) {
	memset(dis, 63, sizeof dis);
	pq.push({0, {x, y}});
	dis[x][y] = 0;
	while (!pq.empty()) {
		int fx = pq.top().second.first, fy = pq.top().second.second;
//		cout << fx << " " << fy << endl;
		pq.pop();
		if (vis[fx][fy]) {
			continue;
		}
		vis[fx][fy] = true;
		if (fy < c && dis[fx][fy + 1] > dis[fx][fy] + a[fx][fy]) {
			dis[fx][fy + 1] = dis[fx][fy] + a[fx][fy];
			pq.push({-dis[fx][fy + 1], {fx, fy + 1}});
		}
		if (fy > 1 && dis[fx][fy - 1] > dis[fx][fy] + a[fx][fy - 1]) {
			dis[fx][fy - 1] = dis[fx][fy] + a[fx][fy - 1];
			pq.push({-dis[fx][fy - 1], {fx, fy - 1}});
		}
		if (fx < r && dis[fx + 1][fy] > dis[fx][fy] + b[fx][fy]) {
			dis[fx + 1][fy] = dis[fx][fy] + b[fx][fy];
			pq.push({-dis[fx + 1][fy], {fx + 1, fy}});
		}
		for (int i = 1; i < fx; i++) {
			if (dis[fx - i][fy] > dis[fx][fy] + 1 + i) {
				dis[fx - i][fy] = dis[fx][fy] + 1 + i;
				pq.push({-dis[fx - i][fy], {fx - i, fy}});
			}
		}
	}
}

signed main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j < c; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i < r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> b[i][j];
		}
	}
	bfs(1, 1);
	cout << dis[r][c];
}

第二版

考虑如何优化第一版的算法。我们考虑一下，第一版的时间复杂度是 \(O(|E|\log|E|)\) ，而 \(|E|\) 可以达到 \(3 \times R^2 \times C\) 的级别，又因为 \(2 \leq R,\, C \leq 500\) ，所以总时间复杂度可以达到 \(10^{10}\) 的级别，这是绝对无法通过的。但是由于算法本身已经足够优秀了。我们只需要考虑做一些简单的优化。

此时我们可以考虑剪枝，由于图中的边权较为固定（除了第四种操作），因此可以考虑计算出答案就返回。这种剪枝方法可以在保证答案无误的情况下，大幅度的调程序运行的效率。

尝试加入剪枝后，你就可以较为轻松的 AC 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <queue>
#include <cstring>

//#define int long long

using namespace std;

bool vis[509][509];
int r, c, a[509][509], b[509][509], dis[509][509];
priority_queue<pair<int, pair<int, int> > > pq;

void bfs(int x, int y) {
	memset(dis, 63, sizeof dis);
	pq.push({0, {x, y}});
	dis[x][y] = 0;
	while (!pq.empty()) {
		int fx = pq.top().second.first, fy = pq.top().second.second;
//		cout << fx << " " << fy << endl;
		pq.pop();
		if (fx == r && fy == c) {
			return;
		}
		if (vis[fx][fy]) {
			continue;
		}
		vis[fx][fy] = true;
		if (fy < c && dis[fx][fy + 1] > dis[fx][fy] + a[fx][fy]) {
			dis[fx][fy + 1] = dis[fx][fy] + a[fx][fy];
			pq.push({-dis[fx][fy + 1], {fx, fy + 1}});
		}
		if (fy > 1 && dis[fx][fy - 1] > dis[fx][fy] + a[fx][fy - 1]) {
			dis[fx][fy - 1] = dis[fx][fy] + a[fx][fy - 1];
			pq.push({-dis[fx][fy - 1], {fx, fy - 1}});
		}
		if (fx < r && dis[fx + 1][fy] > dis[fx][fy] + b[fx][fy]) {
			dis[fx + 1][fy] = dis[fx][fy] + b[fx][fy];
			pq.push({-dis[fx + 1][fy], {fx + 1, fy}});
		}
		for (int i = 1; i < fx; i++) {
			if (dis[fx - i][fy] > dis[fx][fy] + 1 + i) {
				dis[fx - i][fy] = dis[fx][fy] + 1 + i;
				pq.push({-dis[fx - i][fy], {fx - i, fy}});
			}
		}
	}
}

signed main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j < c; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i < r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> b[i][j];
		}
	}
	bfs(1, 1);
	cout << dis[r][c];
}

总结

这道题总体来说还是比较水的，是一个优先队列优化 BFS + 剪枝的还不错的练习题。可以锻炼一下自己的代码能力，毕竟 BFS 写挂的可能性还是非常高的。注意细节和特殊优化即可通过。

#题解 #AtCoder
AT_zone2021_e 题解
https://lixuannan.github.io/posts/41815
作者
CodingCow Lee
发布于
2023年10月20日
许可协议