自动搬运

查看原文

来自洛谷，原作者为

	Spectator 我趁有半天空档 ／ 为你跑一趟 ／ 城市里永远有宝藏

搬运于2025-08-24 22:21:06，当前版本为作者最后更新于2024-10-06 10:29:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的食用体验 $|$ 题目传送门 $|$ 我的其他题解

${\color{#00CD00}\text{题意}}$

给定一张 $n\times m$ 的网格，每个格子 $(i,j)$ 上有一个权值 $a_{i,j}$。可以在网格上任意左右移动，但只有在第 $1$ 列或者第 $m$ 列才能上下移动。现在要从 $(1,1)$ 出发依次经过 $D$ 个不同的格子，求经过的格子的权值之和的最小值。

${\color{#00CD00}\text{思路}}$

将每一个点都作为状态进行考虑显然不现实。注意到“只有在第 $1$ 列或者第 $m$ 列才能上下移动”，不难想到将每一行的第 $1$ 个点和第 $m$ 个点作为状态进行考虑。这样就将原图拆分为了 $2\times n$ 个状态，其中第 $i$ 行第 $1$ 的点的编号为 $i$，第 $i$ 行第 $m$ 的点的编号为 $i+n$。

接下来可以在这些状态之间连边。连边方式也比较显然：
对于第 $i$ 行，

• 从 $i$ 向 $i+n$ 连一条边，权值为 $\sum a_i - a_{i,m}$。
• 从 $i+n$ 向 $i$ 连一条边，权值为 $\sum a_i - a_{i,1}$。
• 若 $i>1$，从 $i$ 向 $i-1$ 连权值为 $a_{i,1}$ 的边，同时从 $i+n$ 向 $i\!-\!1\!+\!n$ 连权值为 $a_{i,m}$ 的边。
• 若 $i<n$，从 $i$ 向 $i+1$ 连权值为 $a_{i,1}$ 的边，同时从 $i+n$ 向 $i\!+\!1\!+\!n$ 连权值为 $a_{i,m}$ 的边。

其中 $\sum a_i$ 表示第 $i$ 行所有 $a_{i,j}$ 的和。减去 $a_{i,m}$ 和 $a_{i,1}$ 是为了避免算重。

这样我们就建出了一张图。定义 $f_{i,j}$ 表示由状态 $i$ 到状态 $j$ 的最小花费时间。可以用多源最短路算法求解。

• 使用 $\bf floyd$ 算法，时间复杂度为 $O(n^3)$，可以通过 $70\%$ 的数据。
• 使用 $\bf Dijkstra$ 算法，以每一个点为原点跑一遍 $\rm dijkstra$，时间复杂度为 $O(n^2\log n)$，可以通过本题。

求得 $f$ 数组后，对于每一个询问 $(tx,ty)\to (x,y)$，分类讨论出最短时间即可。注意不要忘了讨论 $tx=x$ 的情况，即起点与终点在同一行。

代码实现上需要注意：

• long long。
• 数组要开 $2$ 倍大。
• 可以预处理出前缀和、后缀和来优化实现。
• 留意 corner case，避免转角处的点的权值被重复计算或漏算。

本题实现较繁琐，具体细节可参见代码。

${\color{#00CD00}\text{代码}}$

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define req(i, a, b) for(int i=a; i>=b; i--)
#define add(u, v, w) G[u].push_back({v, w})
using namespace std;
const int N = 2e3 + 5, M = 2e2 + 5, inf = 2e9 + 5;
typedef pair<int, int> pii;
long long n, m, Q, ans; //其实只有这个 ans 需要开 long long
int a[N][M], s[N][M], r[N][M];
int vis[N<<1], f[N<<1][N<<1];
vector<pii> G[N<<1];
void dijkstra(int s, int *dis){ //dijkstra 算法 
	priority_queue<pii, vector<pii>, greater<pii>> q;
	fill(dis, dis+1+n*2, inf), fill(vis, vis+1+n*2, 0);
	dis[s] = 0, q.push({0, s});
	while(!q.empty()){
		int d = q.top().first, u = q.top().second; q.pop();
		if(vis[u]) continue; vis[u] = 1;
		for(pii i:G[u]){
			int v = i.first, w = i.second;
			if(d + w < dis[v]) dis[v] = d + w, q.push({dis[v], v});
		}
	}
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n) rep(j, 1, m) cin >> a[i][j]; //读入 
	rep(i, 1, n) rep(j, 1, m) s[i][j] = s[i][j-1] + a[i][j]; //前缀和 
	rep(i, 1, n) req(j, m, 1) r[i][j] = r[i][j+1] + a[i][j]; //后缀和
	rep(i, 1, n){ //建图
		if(i > 1) add(i, i-1, a[i][1]), add(i+n, i-1+n, a[i][m]);
		if(i < n) add(i, i+1, a[i][1]), add(i+n, i+1+n, a[i][m]);
		add(i, i+n, s[i][m] - a[i][m]), add(i+n, i, s[i][m] - a[i][1]);
	}
	rep(i, 1, n*2) dijkstra(i, f[i]); //多源最短路 
	int tx=1, ty=1;
	for(cin >> Q; Q --> 0;){ //分类讨论处理询问 
		int x, y; cin >> x >> y;
		int res0 = tx ^ x ? inf : y < ty ? s[x][ty] - s[x][y] : s[x][y-1] - s[x][ty-1];
		int res1 = s[tx][ty] - a[tx][1] + f[tx][x] + s[x][y] - a[x][y];
		int res2 = r[tx][ty] - a[tx][m] + f[tx+n][x] + s[x][y] - a[x][y];
		int res3 = s[tx][ty] - a[tx][1] + f[tx][x+n] + r[x][y] - a[x][y];
		int res4 = r[tx][ty] - a[tx][m] + f[tx+n][x+n] + r[x][y] - a[x][y];
		ans += min({res0, res1, res2, res3, res4}); tx = x, ty = y;
	}
	cout << ans + a[tx][ty];
	return 0;
}

AC Record

附：本题有一道加强版，那题的时限只有 $200ms$，需要使用 dp 解决。