基础最短路练习题

【题目描述】

给定$n$个点$m$条边的简单无向连通图$G$，边有边权。保证没有重边和自环。

定义一条简单路径的权值为路径上所有边边权的异或和。

保证$G$中不存在简单环使得边权异或和不为$0$。

$Q$次询问$x$到$y$的最短简单路径。

【输入格式】

第一行三个正整数$n,m,Q$。

接下来$m$行，一行三个非负整数$x,y,v（1≤x,y≤n）$，表示一条连接$x,y$，权值为$v$的无向边。保证没有重边和自环。

接下来$Q$行，一行两个正整数$x,y（1≤x,y≤n）$，表示一次询问。

【输出格式】

$Q$行，一行一个整数表示答案。

【样例输入】

3 2 1
1 2 2
2 3 3
1 3

【样例输出】

1

【数据规模与约定】

对于$100\%$的数据，满足$1≤n≤10^5，1≤m≤2n，0≤v<2^{30}$。

【来源】

Luogu P5651