自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:09:18，当前版本为作者最后更新于2019-04-17 20:32:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目地址：P5304 [GXOI/GZOI2019]旅行者

这里是官方题解

一个图 $n$ 点 $m$ 条边，里面有 $k$ 个特殊点，问这 $k$ 个点之间两两最短路的最小值是多少？ $n \leq 10^5, m \leq 5 * 10 ^5$

假设我们把特殊点分成 $A,B$ 两个集合，新建 $s$ 连 $A$ 集合的所有点，边权 $0$ ，新建 $t$ 连接 $B$ 集合里的所有点，边权 $0$ ，那么 $s$ 到 $t$ 的最短路就是 $A,B$ 集合点之间的最短路的最小值。

那么对于 $k$ 个特殊点，我们枚举二进制里的第 $i$ 位，把二进制第 $i$ 位是 $0$ 的点放在 $A$ ， $1$ 的点放在 $B$ ，用以上方法跑一个最短路。

然后跑 $log\ n$ 次最短路之后，所有最短路的最小值就是最终答案。

原理是，假设 $k$ 个特殊点里最近的是 $x$ 和 $y$ ，那么 $x$ 和 $y$ 一定有一个二进制位不一样，那么他们肯定在那次分组的时候被放进了不同的集合，从而肯定被算进了最后的答案之中最短路。

#include <bits/stdc++.h>

const int MAXN = 100010, MAXM = 700010;

struct Edge {
	int y, z;
	Edge *next;
}*a[MAXN], POOL[MAXM], *ptr, *back[MAXN];

void AddEdge(int x, int y, int z) {
	Edge *tmp = ptr++;
	tmp->y = y;
	tmp->z = z;
	tmp->next = a[x];
	a[x] = tmp;
}

int n, nodes[MAXN], k, s, t;
long long dis[MAXN];

long long dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	std::priority_queue<std::pair<long long, int> > Q;
	Q.push(std::make_pair(0, s));
	for (int i = 1; i < n + 2; i++) {
		while (!Q.empty() && dis[Q.top().second] != -Q.top().first) Q.pop();
		if (Q.empty()) break;
		int now = Q.top().second;
		Q.pop();
		for (Edge *p = a[now]; p; p = p->next)
			if (dis[p->y] > dis[now] + p->z)
				Q.push(std::make_pair(-(dis[p->y] = dis[now] + p->z), p->y));
	}
	return dis[t];
}

int main(int argc, char* argv[]) {
	int T;
	scanf("%d", &T);
	while (T--) {
		ptr = POOL;
		memset(a, 0, sizeof a);
		int m;
		scanf("%d%d%d", &n, &m, &k);
		while (m--) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			AddEdge(x, y, z);
		}
		for (int i = 1; i <= k; i++) scanf("%d", nodes + i);

		long long Ans = ~0ull>>1;
		s = n + 1, t = n + 2;
		for (int i = 0; (1 << i) <= k; i++) {
			Edge *backup = ptr;
			memcpy(back, a, (sizeof a[0]) * (n + 3));
			for (int j = 1; j <= k; j++) if (j & (1 << i)) {
					AddEdge(s, nodes[j], 0);
				} else {
					AddEdge(nodes[j], t, 0);
				}
			Ans = std::min(Ans, dijkstra());
			ptr = backup;
			memcpy(a, back, (sizeof a[0]) * (n + 3));
			for (int j = 1; j <= k; j++) if (j & (1 << i)) {
					AddEdge(nodes[j], t, 0);
				} else {
					AddEdge(s, nodes[j], 0);
				}
			Ans = std::min(Ans, dijkstra());
			ptr = backup;
			memcpy(a, back, (sizeof a[0]) * (n + 3));
		}
		printf("%lld\n", Ans);
	}
	return 0;
}