← 返回题目列表

AtCoder · abc410_d

G. 异或最短步行

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

分数: 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 否则。
例如, 3\ \mathrm{XOR}\ 5 = 6 (二进制: 011\ \mathrm{XOR}\ 101 = 110).
一般来说,按位 \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.