自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 21:43:55，当前版本为作者最后更新于2020-07-17 13:28:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Description

P2966
给定一张图，求 $q$ 组询问，$s_i$ 到 $t_i$ 的边权之和与点权的最大值的和的最小值。

Solution

Floyd。

首先是对点权进行排序（记得要记原来的顺序，以便之后跑 floyd）。

然后邻接表存边，floyd 的经典操作。

然后就三重循环跑 floyd 即可，注意 $dist$ 是跑边权，$ans$ 是边权与点权。

我们用上 floyd 的转移公式：

$$dist_{i,j}=\min\{dist_{i,j},dist_{i,k}+dist_{k,j}\} $$

注意，这时候不能直接用 $i,j,k$，因为点权是排过序的，所以都要转变成 $c_i.dis$，$c_j.dis$，$c_k.dis$。

最后 $ans$ 的转移公式就很简单了，按照题目所说的：

$$ans_{i,j}=\min\{ans_{i,j},dist_{i,j}+\max\{c_i.val,c_j.val,c_k.val\}\} $$

跟上面 $dist$ 的转移公式一样，$i,j,k$ 还是要转变为 $c_i.dis$，$c_j.dis$，$c_k.dis$。

最后输出 $ans_{a,b}$ 即可。

注意：上面的 $dis$ 和 $val$ 代表的具体内容可以看下方的代码。

Code 1

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int ans[1005][1005], dist[1005][1005]; 
const int inf = 0x3f3f3f3f;

struct node {
	int val, dis;
} c[1005];

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

int main () {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i].val);
		c[i].dis = i;
	}
	sort(c + 1, c + n + 1, cmp);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			if (i == j) dist[i][j] = 0;
			else dist[i][j] = inf;
	memset(ans, 0x3f, sizeof(ans));
	for (int i = 1, u, v, w; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		dist[u][v] = w;
		dist[v][u] = w;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				dist[c[i].dis][c[j].dis] = min(dist[c[i].dis][c[j].dis], dist[c[i].dis][c[k].dis] + dist[c[k].dis][c[j].dis]);
				ans[c[i].dis][c[j].dis] = min(ans[c[i].dis][c[j].dis], dist[c[i].dis][c[j].dis] + max(c[i].val, max(c[j].val, c[k].val)));
			}
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", ans[a][b]);
	}
	return 0;
}

预测得分：$50$ 分
为什么只有 $50$ 分呢 …… 因为题目中说了可能要有重边
所以我们要处理一下重边

Code 2

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int ans[1005][1005], dist[1005][1005]; 
const int inf = 0x3f3f3f3f;

struct node {
	int val, dis;
} c[1005];

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

int main () {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i].val);
		c[i].dis = i;
	}
	sort(c + 1, c + n + 1, cmp);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			if (i == j) dist[i][j] = 0;
			else dist[i][j] = inf;
	memset(ans, 0x3f, sizeof(ans));
	for (int i = 1, u, v, w; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		dist[u][v] = min(dist[u][v], w);
		dist[v][u] = min(dist[v][u], w);
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				dist[c[i].dis][c[j].dis] = min(dist[c[i].dis][c[j].dis], dist[c[i].dis][c[k].dis] + dist[c[k].dis][c[j].dis]);
				ans[c[i].dis][c[j].dis] = min(ans[c[i].dis][c[j].dis], dist[c[i].dis][c[j].dis] + max(c[i].val, max(c[j].val, c[k].val)));
			}
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", ans[a][b]);
	}
	return 0;
}

预测得分：$100$ 分
AC Link!

By Shuchong
2020.7.17