分数: 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.
一般来说,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