← 返回题目列表

AtCoder · abc396_d

G. 最小异或路径

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

分数: 400 点

问题陈述

给你一个简单的连通无向图 N 顶点编号 1 通过 N 和 M 边编号 1 通过 M。边缘 i 连接顶点 u_i 和 v_i,并且有一个标签 w_i.

从顶点开始的所有简单路径(不会多次经过同一顶点的路径) 1 到顶点 N,找到路径上边的标签的最小异或。

异或注意事项 对于非负整数 A 和 B,他们的异或 A \oplus B 定义如下:
  • 在二进制表示中 A \oplus B,对应位置的数字 2^k \,(k \ge 0) is 1 当且仅当恰好有一个数字位于 A 和 B is 1;否则,就是 0.
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,XOR k 整数 p_1, \dots, p_k 定义为 (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)。可以证明,它与顺序无关 p_1, \dots, p_k.

约束

  • 2 \leq N \leq 10
  • N-1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq u_i < v_i \leq N
  • 0 \leq w_i < 2^{60}
  • 给定的图是一个简单的连通无向图。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M

输出

打印答案。


示例输入 1

4 4
1 2 3
2 4 5
1 3 4
3 4 7

示例输出 1

3

从顶点有两条简单的路径 1 到顶点 4:

  • 1 \to 2 \to 4
  • 1 \to 3 \to 4

第一个路径边缘上的标签的异或为 6,第二条路径是 3。因此,答案是 3.


示例输入 2

4 3
1 2 1
2 3 2
3 4 4

示例输出 2

7

示例输入 3

7 10
1 2 726259430069220777
1 4 988687862609183408
1 5 298079271598409137
1 6 920499328385871537
1 7 763940148194103497
2 4 382710956291350101
3 4 770341659133285654
3 5 422036395078103425
3 6 472678770470637382
5 7 938201660808593198

示例输出 3

186751192333709144