分数: 450 点
问题陈述
给你一个连通的无向图 N 顶点和 M 没有自循环的边,其中顶点编号为 1 to N 和边的编号从 1 to M。边缘 i 连接顶点 u_i 和 v_i 双向且有标签 w_i.
来自顶点的简单路径(不会多次访问同一顶点的路径) 1 到顶点 N,找到按位的最小可能值 路径中包含的边缘上的所有标签的 \mathrm{OR} 。
什么是按位 \mathrm{OR} 操作? 非负整数的
按位 \mathrm{OR} 非负整数的 A 和 B, A\ \mathrm{OR}\ B,定义如下:
- 中的数字 2^k (k \geq 0) 地点 A\ \mathrm{OR}\ B 的二进制表示是 1 如果至少有一位数字 2^k 地点 A 和 B 的二进制表示是 1,和 0 否则。
一般来说,按位 \mathrm{OR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k),并且可以证明这不依赖于顺序 p_1, p_2, p_3, \dots p_k.
约束
- 2\le N\le 2\times 10^5
- N-1\le M\le 2\times 10^5
- 1\le u_i < v_i\le N
- 0\le w_i< 2^{30}
- 给定的图形已连接。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M
输出
输出答案。
示例输入 1
4 5 1 2 1 1 3 4 2 3 2 2 4 4 3 4 3
示例输出 1
3
通过遍历边 1,3,5 按顺序访问顶点 1,2,3,4 按位顺序合计 \mathrm{OR} is 1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 3=3.
按位求和是不可能的 \mathrm{OR} 小于 3,所以输出 3.
示例输入 2
3 5 1 2 1 1 2 2 1 2 3 1 2 4 2 3 4
示例输出 2
4
该图可能包含多边。
示例输入 3
8 12 4 5 16691344 5 7 129642441 2 7 789275447 3 8 335307651 3 5 530163333 5 6 811293773 3 8 333712701 1 2 2909941 2 3 160265478 5 7 465414272 1 3 903373004 6 7 408299562
示例输出 3
468549631