基础最短路练习题
题目背景
YSGH 牛逼
题目描述
给定 $n$ 个点 $m$ 条边的简单无向连通图 $G$,边有边权。保证没有重边和自环。
定义一条简单路径的权值为路径上所有边边权的异或和。
保证 $G$ 中不存在简单环使得边权异或和不为 $0$。
$Q$ 次询问 $x$ 到 $y$ 的最短简单路径。
输入输出格式
输入格式
第一行三个正整数 $n, m, Q$。
接下来 $m$ 行,一行三个非负整数 $x, y, v$($1 \le x, y \le n$),表示一条连接 $x, y$,权值为 $v$ 的无向边。保证没有重边和自环。
接下来 $Q$ 行,一行两个正整数 $x, y$($1 \le x, y \le n$),表示一次询问。
输出格式
$Q$ 行,一行一个整数表示答案。
输入输出样例
输入样例 #1
3 2 1
1 2 2
2 3 3
1 3
输出样例 #1
1
说明
| 数据点编号 | $n, Q \le$ | 特殊性质 |
| :--: | :--: | :--: |
| $1,2$ | $10$ | 无 |
| $3,4$ | $20$ | 无 |
| $5,6$ | ${10}^5$ | $m = n - 1$ |
| $7,8$ | ${10}^5$ | $v \le 1$ |
| $9,10$ | ${10}^5$ | 无 |
对于 $100\%$ 的数据,满足 $1 \le n \le {10}^5$,$1 \le m \le 2n$,$0 \le v < 2^{30}$。