图论 - 某进制分组 - P5304 旅行者

P5304旅行者

\(\mathtt{TAGS}\)： 多源多汇最短路，二进制分组
\(\mathtt{ESTIMATION}\)：非常好二进制分组，让我的大脑旋转

题意简述

给定 \(k\) 个点和一张有向图，求以这 \(k\) 个点为起点和终点的最短路中最短的一条的长度。

First. 怎么求多源多汇最短路

solution.1

超级源点和超级汇点，超级源点以 \(0\) 的权值连接所有起点，所有终点以 \(0\) 的权值连向超级汇点，从超级源点出发，到超级汇点，即为多源多汇的最短路的长度。

solution.2

对于 dijkstra 算法，直接把所有源点初始放进 \(s\) 集合里，\(dis\) 设为 \(0\)，正常跑一遍即可。

But，这道题的起点和终点是不固定的！

所以第一种做法先暂不考虑。

Second. 怎么分起点终点

*MikeZ = & shuffle

直接 shuffle，随机分组！
-- by MikeZ

很不幸的是，这题没有很多时间让你反复跑随机化来获得正确答案，正确率不高。

二进制分组

对于每个标记的节点 \(u\)，考虑它的二进制表示法，按照每一位二进制为 \(0\) 或是 \(1\) 来确定它是哪个集合的。而且由于二进制某一位不同的数一定就不相等，所以不会出现起点 = 终点的情况。

Code

const int N = 2e5 + 10;
int n, m, k;
vector< pi > G[N];
ll dis[N];
bool vis[N];
int li[N];
ll dijkstra (int pos, int val) { // pos 表示 二进制的第几位，val表示是1为S集还是 0 为 S 集
	priority_queue<pi, vector<pi>, greater<pi> > q;
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= k; i ++) {
		int x = li[i];
		if(((x >> (pos - 1)) & 1) == val) {
			dis[x] = 0;
			q.push({0, x});
		}
	}
	while(!q.empty()) {
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for (auto e : G[u]) {
			int v = e.first, w = e.second;
			if(dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
	ll minn = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= k; i ++) {
		int x = li[i];
		if(((x >> (pos - 1)) & 1) != val) {
			minn = min(dis[x], minn);
		}
	}
	return minn;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) G[i].clear();
		for (int i = 1; i <= m; i ++) {
			int u, v, w;
			cin >> u >> v >> w;
			G[u].push_back({v, w});
		}
		cin >> k;
		for (int i = 1; i <= k; i ++) cin >> li[i];
		ll ans = 0x3f3f3f3f3f3f3f3f;
		for (int i = 0; i < 24; i ++) { // 枚举二进制位数
			ans = min(ans, dijkstra(i, 0));
			ans = min(ans, dijkstra(i, 1));
		}
		if(ans == 0x3f3f3f3f3f3f3f3f) cout << -1 << '\n';
		else cout << ans << '\n';
	}
	return 0;
}