#1299. 基础最短路练习题

基础最短路练习题

题目描述

给定 nn 个点 mm 条边的简单无向连通图 GG,边有边权。保证没有重边和自环。

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

保证 GG 中不存在简单环使得边权异或和不为 00。

QQ 次询问 xx 到 yy 的最短简单路径。

输入格式

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

接下来 mm 行,一行三个非负整数 x,y,vx, y, v(1≤x,y≤n1 \le x, y \le n),表示一条连接 x,yx, y,权值为 vv 的无向边。保证没有重边和自环。

接下来 QQ 行,一行两个正整数 x,yx, y(1≤x,y≤n1 \le x, y \le n),表示一次询问。

输出格式

QQ 行,一行一个整数表示答案。

样例

3 2 1
1 2 2
2 3 3
1 3
1

题目来源:洛谷 P5651