91 人解决,133 人已尝试。
121 份提交通过,共有 758 份提交。
4.2 EMB 奖励。
单点时限: 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$,分别表示起点和终点。
可能有重边和自环。
在一行中输出一个最小代价,如果无解输出 $-1$。
3 4 1 2 2 1 2 4 1 3 5 2 3 3 1 2
2
图中可能会有重边。
91 人解决,133 人已尝试。
121 份提交通过,共有 758 份提交。
4.2 EMB 奖励。