← 返回题目列表

AtCoder · abc408_e

H. 最小或路径

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

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