自动搬运

查看原文

来自洛谷，原作者为

	浮尘ii **

搬运于2025-08-24 21:51:08，当前版本为作者最后更新于2019-03-19 22:59:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

根本不需要最短路算法，这是一个无权图最短路，所以直接 BFS 就行。

也不需要显式建图，直接 BFS 转移即可。

状态 $(i,j)$ 表示，当前在第 $i$ 个点，当前的 doge 跳跃能力为 $j$。

当 $j \le \sqrt{n}$ 时，只有 $n \sqrt{n}$ 个状态。

当 $j \gt \sqrt{n}$ 时，只有 $m \sqrt{n}$ 个状态（最多有 $m$ 只 doge，每只 doge 只有 $\frac{n}{j}\lt \sqrt{n}$ 个可行位置）。

$(i,j)$ 可以转移到 $(i-j, j)(i-j\ge0)$ 和 $(i+j,j) (i+j\lt n)$，同时对于第一次访问到的 $i$，把初始在 $i$ 的所有 doge 加入队列。

状态判重时使用 std::set 会 TLE，可以用 hash 或者 std::bitset。

时间复杂度 $O((n+m)\sqrt{n})$。

另外原题数据有点水，同时洛谷只取了原题的很少一部分数据所以更水，建议大家去 UOJ 提交此题以进一步检验程序正确性。

#include <queue>
#include <tuple>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>

const int maxN = 30005;

int N, M, S, T;
std::vector<int> Doge[maxN];
std::queue<std::tuple<int, int, int>> Q;
std::bitset<maxN> vis[maxN];
bool Vis[maxN];

void insert(int i, int p, int step)
{
	if (!Vis[i])
	{
		Vis[i] = true;
		for (auto x : Doge[i])
			if (!vis[i].test(x))
				vis[i].set(x), Q.emplace(i, x, step);
	}
	if (!vis[i].test(p))
		vis[i].set(p), Q.emplace(i, p, step);
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0, b, p; i != M; ++i)
	{
		scanf("%d%d", &b, &p);
		if (i == 0)
			S = b;
		if (i == 1)
			T = b;
		Doge[b].push_back(p);
	}

	if (S == T)
	{
		puts("0");
		return 0;
	}

	Vis[S] = true;
	for (auto x : Doge[S])
		if (!vis[S].test(x))
		{
			vis[S].set(x);
			Q.emplace(S, x, 0);
		}

	while (!Q.empty())
	{
		int i, p, step;
		std::tie(i, p, step) = Q.front();
		Q.pop();
		if (i - p == T || i + p == T)
		{
			printf("%d\n", step + 1);
			return 0;
		}
		if (i - p >= 0)
			insert(i - p, p, step + 1);
		if (i + p < N)
			insert(i + p, p, step + 1);
	}

	puts("-1");

	return 0;
}