P11564 【MX-X7-T5】[LSOT-3] 你的列车是生存战略

原题链接：。 >啊啊 我搭上了那趟列车$\\$无论被业火灼烧多少次$\\$或是化作灰烬$\\$为何我要如此$\\$因为这是通往你的道路$\\$就算事与愿违也好$\\$还是听天由命也罢$\\$我将要改写这个世界$\\$

Ringo 要带着企鹅罐乘坐列车前往命运所至之地寻找 Shyouma 并且完成命运换乘！ 她可以通过乘坐列车在冰之世界的 $n$ 个车站中穿行，车站编号为 $1 \sim n$。 每一个车站都有两个标号，第 $i$ 个车站的标号分别为 $c_i$ 和 $d_i$。 冰之世界中一共有普通列车和特快列车两种列车。 - 任意两地之间都有一条**可以往返**的普通列车的线路，车站 $i$ 与车站 $j$ 之间的线路所花费的时间为 $\min(a_{c_i \mathbin{|} c_j},b_{d_i \mathbin{\&} d_j})$（$\mathbin{|}$ 表示按位或，$\mathbin{\&}$ 表示按位与）。**保证 $\boldsymbol{a}$ 单调不降，$\boldsymbol{b}$ 单调不升。** - 特快列车一共有 $m$ 条线路，第 $i$ 条是从车站 $u_i$ **驶向**车站 $v_i$ 的**单向线路**，所花费的时间为 $w_i$。 Ringo 希望能更快找到 Shyouma，不然世界就要毁灭了！ Ringo 开始的时候在车站 $1$，但是她不知道命运所至之地到底在哪里。所以她想知道对于每一个车站，如果 Shyouma 在那里，她最少需要花多少时间到达 Shyouma 所在的位置。

无

无

> 生存戦略、しましょうか **【样例解释 #1】** Ringo 开始的时候就在车站 $1$，所以到车站 $1$ 最少的花费的时间为 $0$。 到车站 $2$ 的花费最少时间的路径为乘坐从 $1$ 到 $2$ 的普通列车，花费的时间为 $\min(a_{c_1 \mathbin{|} c_2},b_{d_1 \mathbin{\&} d_2})=\min(a_3,b_0)=\min(4,8)=4$。 到车站 $3$ 的花费最少时间的路径为乘坐从 $1$ 到 $3$ 的普通列车，花费的时间为 $4$。 到车站 $4$ 的花费最少时间的路径为乘坐从 $1$ 到 $3$ 的普通列车，花费的时间为 $4$，随后乘坐第 $3$ 条特快列车花费 $2$ 的时间从 $3$ 到 $4$，总花费时间为 $4+2=6$。 到车站 $5$ 的花费最少时间的路径为乘坐从 $1$ 到 $5$ 的普通列车，花费的时间为 $7$。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（10 分）：$n\le 1000$。 - 子任务 2（10 分）：$k=0$。 - 子任务 3（20 分）：$a_i=i$，$b_i=10^{18}$。 - 子任务 4（20 分）：$m=0$，$n \ge 2$，$c_{n-1}=d_{n-1}=0$，$c_n=d_n=2^k-1$。 - 子任务 5（20 分）：$n=m=2^k$。 - 子任务 6（20 分）：无特殊限制。 对于全部的数据，$1\le n\le 10^6$，$0\le m\le10^6$，$0\le k\le 14$，$0\le c_i,d_i< 2^k$，$0\le a_i,b_i,w_i\le 10^{18}$，$1\le u_i,v_i\le n$，$a$ 单调不降，$b$ 单调不升。