3483. 最小 OR 路径 (EASY)

单测试点时限: 2.0 秒

内存限制: 512 MB

给定一个有 个点和 条边的无向图,其中每一条边 都有一个权值记为

对于给出的两个点 ,求一条 的路径,使得路径上的边权的 OR(位或)和最小,输出这个值。(也就是说,如果将路径看做边的集合 ,那么这条路径的代价为 ,现在求一条路径使得其代价最小,输出这个代价。) 如果不存在这样的路径,输出

输入

第一行两个数
接下来 行,每行三个数 ,表示有一条 的权值为 的无向边。
最后一行两个数 ,分别表示起点和终点。

可能有重边和自环。

输出

在一行中输出一个最小代价,如果无解输出

样例

Input
3 4
1 2 2
1 2 4
1 3 5
2 3 3
1 2
Output
2

提示

图中可能会有重边。

49 人解决,90 已尝试。

58 份提交通过,共有 276 份提交。

7.6 EMB 奖励。

创建: 10 月,4 周前.

修改: 10 月,3 周前.

最后提交: 7 月,2 周前.

来源: EOJ Monthly 2018.1

标签