自动搬运

查看原文

来自洛谷，原作者为

	lmz105 已经看到我们学校对面的在学校（直线距离不超过100米）向我招手|一个平平无奇普普通通的FVV(以刷水题为生,永远不做外国题（已取消，because不会一直UKE了（已取消，because又UKE了）））

搬运于2025-08-24 21:18:24，当前版本为作者最后更新于2025-04-07 19:04:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

这题可以直接把除 $N$ 以外的每个点当作起点，然后求起点到 $N$ 的距离，但是这样太慢了，我们可以看到这是一个无向图，而且终点都是 $N$，所以可以直接把 $N$ 当作起点，求它到每个点的距离，这样就可以快速得到答案。

代码

#include <bits/stdc++.h>
#define ll long long
//#define rw() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef rw()
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

namespace FX {
	template<typename T> inline void r(T &in) {
		in = 0;
		bool bo = 0;
		char ch = getchar();
		while (!isdigit(ch)) {
			bo ^= (ch == '-');
			ch = getchar();
		}
		while (isdigit(ch))
			in = (in << 1) + (in << 3) + (ch ^ 48), ch = getchar();
		if (bo) {
			in = -in;
		}
	}
	template<typename T> inline void w(T out) {
		static char op[20];
		int top = 0;
		if (out < 0) {
			putchar('-');
			do {
				op[++top] = -(out % 10) + 48, out /= 10;
			} while (out);
		} else {
			do {
				op[++top] = out % 10 + 48, out /= 10;
			} while (out);
		}
		while (top)
			putchar(op[top--]);
		putchar(' ');
	}
	template<typename T, typename... Ts> inline void r(T &in, Ts &... ins) {
		r(in), r(ins...);
	}
	template<typename T, typename... Ts> inline void w(T out, Ts... outs) {
		w(out), w(outs...);
	}
	inline void w(const char *p) {
		while (*p) {
			putchar(*p++);
		}
	}
}
using namespace FX;
#undef getchar
#undef putchar
#endif
using namespace std;
const ll N = 106;
ll n, m, dis[N];
vector<ll>e[N];

int main() {
	r(n, m);
	while (m--) {
		ll x, y;
		r(x, y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	memset(dis, -1, sizeof dis);
	queue<ll>q;
	dis[n] = 0;
	q.push(n);
	while (q.size()) {
		ll a = q.front();
		q.pop();
		for (auto v : e[a]) {
			if (dis[v] == -1) {
				dis[v] = dis[a] + 1;
				q.push(v);
			}
		}
	}
	for (ll i = 1; i < n; i++) {
		w(dis[i]);
	}
	return 0;
}

时间复杂度

$O(n)$