分数: 400 点
问题陈述
有一个有向图 N 顶点和 M 边,其中顶点编号为 1 to N 和边的编号从 1 to M。边缘 i 是从顶点开始的有向边 A_i 到顶点 B_i 与 重量 W_i.
求按位的最小值 \mathrm{XOR} 从顶点开始的步行中包含的边的权重 1 到顶点 N.
什么是从顶点步行 1 到顶点 N?
直观地说,它是“从顶点 1 到顶点 N 可能会多次访问同一顶点或边。” 形式上,它是一个边序列 (e_1,\ldots,e_k) 满足以下所有条件:
- e_1 从顶点开始 1.
- 对于所有人 1 \leq i < k,端点 e_i 和起点 e_{i+1} 是相同的。
- e_k 结束于顶点 N.
什么是按位 \mathrm{XOR} 操作?
按位 \mathrm{XOR} 非负整数 A 和 B,表示 A\ \mathrm{XOR}\ B,定义如下:
- 当 A\ \mathrm{XOR}\ B 以二进制形式写入,位于的数字 2^k 地点(k \geq 0) 是 1 如果正好是位于的数字之一 2^k 地点 A 和 B 是 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k),并且可以证明这不依赖于顺序 p_1, p_2, p_3, \dots p_k.
约束
- 2 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq A_i,B_i \leq N
- 0 \leq W_i < 2^{10}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 W_1 A_2 B_2 W_2 \vdots A_M B_M W_M
输出
如果没有从顶点开始的步行 1 到顶点 N,输出 -1.
如果有从顶点开始的步行 1 到顶点 N,输出按位的最小值 \mathrm{XOR} 包含在这样的步行中的边的权重。
示例输入 1
3 3 1 2 4 2 3 5 1 3 2
示例输出 1
1
按位 \mathrm{XOR} 包含在行走中的边的权重(边 1,边缘 2) 是 1.
示例输入 2
4 4 1 4 7 4 2 2 2 3 4 3 4 1
示例输出 2
0
按位 \mathrm{XOR} 包含在行走中的边的权重(边 1,边缘 2,边缘 3,边缘 4) 是 0.
请注意,行走可能包括顶点 N 在中间。
示例输入 3
999 4 1 2 9 2 1 8 1 2 7 1 1 6
示例输出 3
-1
如果没有从顶点开始的步行 1 到顶点 N,输出 -1.