3462. 最小 OR 路径

单点时限: 3.0 sec

内存限制: 512 MB

给定一个有 $n$ 个点和 $m$ 条边的无向图,其中每一条边 $e_i$ 都有一个权值记为 $w_i$。

对于给出的两个点 $a$ 和 $b$,求一条 $a$ 到 $b$ 的路径,使得路径上的边权的 OR(位或)和最小,输出这个值。(也就是说,如果将路径看做边的集合 ${e_1, e_2, \dots, e_k}$,那么这条路径的代价为 $w_1 \; \mathrm{OR} \; w_2 \; \mathrm{OR} \; \dots \; \mathrm{OR} \; w_k$,现在求一条路径使得其代价最小,输出这个代价。) 如果不存在这样的路径,输出 $-1$。

输入格式

第一行两个数 $n$ 和 $m$。
接下来 $m$ 行,每行三个数 $u_i, v_i, w_i$,表示有一条 $u_i$ 到 $v_i$ 的权值为 $w_i$ 的无向边。
最后一行两个数 $a, b$,分别表示起点和终点。

  • $2\le n \le 10^4, 0 \le m \le 10^6, 0 \le w_i \le 2^{62}-1$
  • $1\le u_i, v_i, a, b \le n, a \neq b$

可能有重边和自环。

输出格式

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

样例

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

提示

图中可能会有重边。

91 人解决,133 人已尝试。

121 份提交通过,共有 758 份提交。

4.2 EMB 奖励。

创建: 6 年,11 月前.

修改: 5 年,2 月前.

最后提交: 1 年前.

来源: EOJ Monthly 2018.1

题目标签