自动搬运

查看原文

来自洛谷，原作者为

	Moonlight_dreams “那你就不要哭了，女孩子要笑才好看嘛…” || ”风是他对抗敌人的武器，但在她这里是抚平眼泪的爱意…“|| 粉蝶落金铃，蝶死金铃碎… || 本人是喜美圈的西梅汁~~ || ʕ̢̣̣̣̣̩·͡˔·ོɁ̡̣̣

搬运于2025-08-24 23:12:24，当前版本为作者最后更新于2025-05-06 20:30:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目

代码思路

其实这是一个比较模版的 Floyd 算法的题目。。。

首先，什么是 Floyd

Floyd 就是这是一个图算法，用于求解图中每对顶点之间的最短路径问题。这是一个经典的动态规划算法，用来解决图中任意两个顶点对间最小路径的问题。

解决思路

首先是初始化：

将 $dij$ 数组全部设为无限大，因为我们需要求的是最小路径。然后循环 $n$ 次，每次将 $dij_{i,i}$ 赋值为 1。

接着就是将输入的 $dij_{u , v}$ 和 $dij_{v , u}$ 都设为边权。

接着就是运用 Floyd 算法，计算 $dij$ 数组（计算的公式是 dij[x][y] = min(dij[x][y] , dij[x][k] + dij[k][y]);）。

最后就是输出答案。

AC 代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505 , M = 1e5 + 5;
int dij[N][N];
struct stu
{
	int x , y , val;
}s[M];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n , m;
	cin >> n >> m;
	memset(dij , 0x3f , sizeof dij);
	for (int i = 1; i <= n; i++)
	{
		dij[i][i] = 0;
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> s[i].x >> s[i].y >> s[i].val;
		int u = s[i].x , v = s[i].y , w = s[i].val;
		dij[u][v] = dij[v][u] = min(dij[u][v] , w);
	}
	for (int k = 1; k <= n; k++)
	{
		for (int x = 1; x <= n; x++)
		{
			for (int y = 1; y <= n; y++)
			{
				dij[x][y] = min(dij[x][y] , dij[x][k] + dij[k][y]);
			}
		}
	}
	for (int i = 1; i <= m; i++)
	{
		if (dij[s[i].x][s[i].y] < s[i].val)
		{
			cout << "No";
			return 0;
		}
	}
	cout << "Yes" << endl;
	for (int i = 1; i <= m; i++)
	{
		cout << s[i].val << " ";
	}
	return 0;
}