【最短路 Floyd】最优路线

题意

给定一张\(n\)个点\(m\)条边的无向图，无重边无自环，每个点有点权，每条边有边权。
我们定义一条路径的权值，为这条路径经过的点权最大值乘以边权最大值。
对于每个点对\((u,v)\)，你都要求出\(u,v\)之间的权值最小的路径的权值。

数据范围：\(1 \leq n \leq 500,0 \leq m \leq \frac{n\times (n-1)}2\)，边权和点权不超过\(10^9\)。

思路

看到数据范围很容易联想到\(floyd\)。
如果限定点权从小到大，只有不超过这个点权的点能经过，用限定的这个点权大小更新答案。时间复杂度是\(O(n^4)\)的。
考虑\(floyd\)的本质：\(k,i,j\)三层循环中，\(f_{i,j}\)表示的是经过编号不超过\(k\)的点时\(i,j\)的最短路。
对于本题，可以让\(k\)按点权从小到大枚举点，即限定了点权从小到大，这样做就是\(floyd\)的复杂度了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

struct node {
	int v, id;
}a[501];
int n, m;
int val[501], f[501][501], ans[501][501];

bool cmp(node x, node y) {
	return x.v < y.v;
}

signed main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i].v), a[i].id = i, val[i] = a[i].v;
	memset(f, 127 / 3, sizeof(f));
	memset(ans, 127 / 3, sizeof(ans));
	for (int i = 1, x, y, w; i <= m; i++) {
		scanf("%lld %lld %lld", &x, &y, &w);
		f[x][y] = f[y][x] = w;
		ans[x][y] = ans[y][x] = w * std::max(val[x], val[y]);
	}
	std::sort(a + 1, a + n + 1, cmp);
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j)
					if (f[i][j] > std::max(f[i][a[k].id], f[a[k].id][j]))
						f[i][j] = std::max(f[i][a[k].id], f[a[k].id][j]),
						ans[i][j] = std::min(ans[i][j], f[i][j] * std::max(val[a[k].id], std::max(val[i], val[j])));
	for (int i = 1; i <= n; i++, printf("\n"))
		for (int j = 1; j <= n; j++)
			if (i == j)
				printf("0 ");
			else
				if (ans[i][j] == 707406378)
					printf("-1 ");
			else 
				printf("%lld ", ans[i][j]);
}

【最短路 Floyd】最优路线

原文：https://www.cnblogs.com/HSZGB/p/14084923.html