题目描述

在 LibreOJ，本题仅保证使用 GNU C++17 编译将得到预期的编译结果，使用其他编译器版本不保证编译结果一定符合预期。

3742 年已经到来，现在轮到赛博乐园主办 APIO 了。在这个世界上有 $N$ 个国家，这些国家由 $0$ 到 $N - 1$ 标号，还有 $M$ 条双向道路（每条边双向都可以通行），这些道路由 $0$ 到 $M - 1$ 标号。每条道路连接两个不同的国家，$x[i]$ 和 $y[i]$，并需要花费时间 $c[i]$ 来通过该道路。除了你所在的国家的选手，所有选手都已经聚集在赛博乐园参加 APIO 了。你生活在国家 $0$，而赛博乐园是国家 $H$。你作为你的国家最聪明的人，你的帮助刻不容缓。更具体地，你需要确定从你的国家到达赛博乐园所需的最少时间。

在经过有些国家时，你可以清除你的当前总通过时间。此外，还有些国家在你经过他们时可以将你的当前总通过时间除以 $2$（我们称之为「除以 $2$ 的能力」）。你可以重复经过一个国家。每次你经过一个国家时，你可以选择是否使用这个国家的特殊能力。但你每次经过一个国家时最多可以使用一次特殊能力（如果你多次经过一个国家，你每次经过都可以使用至多一次该国家的特殊能力）。此外，为了防止被赛博乐园化学基金会抓住，你最多只能使用「除以 $2$ 的能力」$K$ 次。一旦你到达赛博乐园，你就不能移动到其他任何地方，因为伟大的 APIO 竞赛即将开赛了！

给出一个数组 $arr$，其中 $arr[i]$ 表示国家 $i\ (0 \le i \le N - 1)$ 的特殊能力。每个国家有下面 $3$ 种特殊能力之中的一种：

• $arr[i] = 0$，意思是这个国家可以让当前总通过时间为 $0$。
• $arr[i] = 1$，表示这个国家不会改变你的当前总通行时间。
• $arr[i] = 2$，表示这个国家拥有让当前总通行时间除以 $2$ 的能力。

保证 $arr[0] = arr[H] = 1$ 成立。换句话说，赛博乐园和你所在的国家没有任何特殊能力。

你的国家不希望错过 APIO 的任何时刻，所以你需要找到到达赛博乐园的最短时间。如果你不能到达赛博乐园，你的答案应该是 $-1$。

实现细节

请在程序开头引入库 cyberland.h。

#include "cyberland.h"

你需要实现以下函数：

double solve(int N, int M, int K, int H, 
    std::vector<int> x, std::vector<int> y, 
    std::vector<int> c, std::vector<int> arr);

• $N$：国家的数量。
• $M$：双向道路的数量。
• $K$：「除以 $2$ 的能力」的最大使用次数。
• $H$：国家「赛博乐园」的标号。
• $x,y,c$：三个长度为 $M$ 的数组。三元组 $(x[i],y[i],c[i])$ 表示第 $i$ 条用来连接国家 $x[i]$ 和 $y[i]$ 的双向边，通过它的时间消耗是 $c[i]$。
• $arr$：一个长度为 $N$ 的数组。$arr[i]$ 表示国家 $i$ 的特殊能力。
• 如果你能到达赛博乐园，调用该函数应返回从你的国家到达赛博乐园的最短时间，如果你不能，则返回 $-1$。
• 这个过程可能会被多次调用。

假设选手的答案为 $ans_1$，标准输出为 $ans_2$，当且仅当 $\dfrac{|ans_1-ans_2|}{\max\{ans_2,1\}}\le 10^{-6}$ 时你的输出被视为是正确的。

注意：由于函数调用可能会发生多次，选手需要注意之前调用的残余数据对于后续调用的影响。

1
3 2 30
2
1 2 1
1 2 12
2 0 4

4.00000000000

1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4

2.00000000000

约束条件

• $2 \le N \le 10^5 , \sum N \le 10^5$
• $0 \le M \le \min\{10^5, \frac{N(N-1)}{2}\}, \sum M \le 10^5$
• $1 \le K \le 10^6$
• $1 \le H < N$
• $0 \le x[i],y[i] < N,x[i] \neq y[i]$
• $1 \le c[i] \le 10^9$
• $arr[i] \in \{0,1,2\}$
• 保证每两个国家之间至多使用一条道路进行连接

子任务

1. （$5$ 分）：$N \le 3, K \le 30$
2. （$8$ 分）：$M = N - 1, K \le 30, arr[i] = 1$，你可以通过这 $M$ 条道路从任意国家到另外一个国家
3. （$13$ 分）：$M = N - 1, K \le 30, arr[i] \in \{0,1\}$，你可以通过这 $M$ 条道路从任意国家到另外一个国家
4. （$19$ 分）：$M = N - 1, K \le 30, x[i] = i, y[i] = i + 1$
5. （$7$ 分）：$K \le 30, arr[i] = 1$
6. （$16$ 分）：$K \le 30, arr[i] \in \{0,1\}$
7. （$29$ 分）：$K \le 30$
8. （$3$ 分）：没有特殊限制

评测程序示例

评测程序示例读取如下格式的输入：

• 第 $1$ 行：$T$

对于 $T$ 组测试数据中的每一个：

• 第 $1$ 行：$N\ M\ K$
• 第 $2$ 行：$H$
• 第 $3$ 行：$arr[0]\ arr[1]\ arr[2]\ \ldots \ arr[N − 1]$
• 第 $4 + i\ (0 \le i \le M - 1)$ 行：$x[i]\ y[i]\ z[i]$

评测程序示例按照如下的格式打印你的答案：

对于每组测试数据：

• 第 $1$ 行: 调用 solve 的返回值