← 返回题目列表

AtCoder · kupc2012_11

K. 异或走廊

中文机器翻译题面 查看原题

問題文

KU 大学流行一种独特的拉力赛。 本次比赛的赛道包括N 休息区和 有 M 路径,i 路径是 f_i 第一个休息站和 t_i 个休息区之间。 每条路都有一个检查站 当你通过 i 检查站时,无论你往哪个方向走, p_i 的分数使用 XOR 相加。与异或 添加了。我说了两遍,因为这很重要。

在这个游戏中,你可以多次通过相同的休息区和道路。 即使达到了目标,还可以继续集会,但是 禁止绕过沿途检查站到达其他休息区。 所以,它之所以如此受欢迎,是因为你必须认真思考走什么路线才能获得高分。

这次 有 Q 参与者, 第j 位参与者是 从 a_j 处的休息区开始,到 看来我们要去 b_j 休息区。 作为管理方,我决定提前研究一下每个参与者的最高分。

入力形式

输入按以下格式给出。其余区域编号为 0 索引。 输出

N M Q
f_1 t_1 p_1
...
f_M t_M p_M
a_1 b_1
...
a_Q b_Q

出力形式

Q 行, 从第j 行是 代表 a_j 个休息站出发 输出到第 b_j 个休息站的路线上获得的最高分数。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq f_i, t_i \lt N, f_i \neq t_i
  • 0 \leq p_i \lt 2^{60}
  • 0 \leq a_j, b_j \lt N
  • 您可以从任何休息站沿着道路到达任何休息站。
  • 休憩所 f_i,t_i 至多有一条路径连接两者。
  • 所有输入值都是整数。

针对该问题的判断设置了一组60分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。

  • M \leq 20

入出力例

入力例1

5 5 3
0 1 7
1 2 22
2 3 128
3 4 128
4 2 128
0 1
0 0
3 4

出力例1

135
128
128

作者:森悟
测试员:田村一则