自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 21:13:47，当前版本为作者最后更新于2021-10-31 21:04:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，观察此题的数据范围 $1\le n,m \le 2 \times 10^3$ 并且 $-10^9 \le w_i \le 10^9$，说明这是一道带有负边权的单源最短路问题，并且我们可以用一个 $O(nm)$ 的算法来进行求解。在这种情况下，相对于 spfa，我选择了更为容易实现的 Bellman_Ford。

Bellman_Ford 算法的思路是这样的。令 $d_i$ 为从节点 $1$ 到节点 $i$ 的最短路。扫描所有边 $(x, y, z)$，如果 $d_y > d_x +z$，那么令 $d_y = d_x + z$。如此这样扫描 $m$ 条边，每条边都扫描 $n$ 次，便得到了最短路的值。

而 spfa 则是该算法的一个队列优化。使用队列可以有效避免不需要扫描的节点的扫描，优化了效率，但是写起来更麻烦，极端情况下效率也未必比前者高。并且此题数据范围小，Bellman-Ford完全可以胜任。

当然，我们还可以加一个小优化，就是当循环次数还没有到 $n$ 次时，如果有一次循环中一个节点的最短路值都没有更新，那么就直接跳出循环。（虽然这个优化可能没什么用）

跑的还挺快，21ms。

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long dis[2010];
struct P {
	int x, y, z;
} a[2010];
int main() {
	scanf("%d%d", &n, &m);
	bool flag = 1;
	for (register int i = 1; i <= n; ++i) dis[i] = 1e18;
	dis[1] = 0;
	for (register int i = 1; i <= m; ++i) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
	for (register int i = 1; i <= n; ++i) {
		flag = 1;
		for (register int j = 1; j <= m; ++j)
			if (dis[a[j].y] > dis[a[j].x] + a[j].z) flag = 0, dis[a[j].y] = dis[a[j].x] + a[j].z;
		if (flag) break;
	}
	for (register int i = 1; i <= n; ++i) printf("%lld ", dis[i] == 1e18 ? -1 : dis[i]);
}