基础最短路练习题

https://www.luogu.com.cn/problem/P5651

本题是假的最短路！

以下设 $w_{ij}$ 为边 $(i,j)$ 的边权，$d(u,v)$ 为点 $u$ 到点 $v$ 的最短异或路径值。

 

首先要说一个性质：

以上说的“最短异或路径”其实是任意路径。

即任意从 $u$ 到 $v$ 的路径异或和相等。

若从 $u$ 到 $v$ 有大于一条路径，则必定有环，如下图。

$d_1(1,7)=w_{1,2} \bigoplus w_{2,4} \bigoplus w_{4,5} \bigoplus w_{5,6} \bigoplus w_{6,3} \bigoplus w_{3,7}$

$d_2(1,7)=w_{1,2} \bigoplus w_{2,3} \bigoplus w{3,7}$

又由于题中特意提到的 “保证G中不存在简单环使得边权异或和不为0。”

所以环中所有边异或和为0，则 $w_{2,4} \bigoplus w_{4,5} \bigoplus w_{5,6} \bigoplus w_{6,3} \bigoplus w_{2,3}=0$

由异或的性质，$d_1=d_2$.

 

则引出下一个性质：

$$d(u,v)=d(s,u) \bigoplus d(s,v)$$

其中 $s$ 为除 $u,v$ 外任意点。

因为由性质1，总能把从 $s$ 到 $v$ 的路径等价转换为 $s->u->v$ 的路径。

则 $d(s,u) \bigoplus d(s,v)=d(s,u) \bigoplus (d(s,u) \bigoplus d(u,v))=d(u,v)$

 

至此，思路就完整了。

任意找一个点 $s$，跑一次bfs。

注意这里的并不需要是最短路，因为只要任意一条路径到达就可以了。

当然要套最短路也可以，就是注意要开long long。

对于每次询问，答案就是 $d(u) \bigoplus d(v)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, Q;
struct edge
{
	int v, w;
};
vector<edge>G[maxn];
int d[maxn];
int vis[maxn];
void bfs(int s) {
	queue<int>que;
	que.push(s);
	while (!que.empty()) {
		int u = que.front(); que.pop();
		if (vis[u])continue;
		vis[u] = 1;
		for (edge e : G[u]) {
			int v = e.v, w = e.w;
			if (!vis[v]) {
				d[v] = (d[u] ^ w);
				que.push(v);
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &Q);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(edge{ v,w });
		G[v].push_back(edge{ u,w });
	}
	bfs(1);
	for (int i = 0; i < Q; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		printf("%d\n", d[u] ^ d[v]);
	}
	return 0;
}