{"problem":{"name":"[APIO2023] 赛博乐园 / cyberland","description":{"content":"3742 年已经到来，现在轮到赛博乐园主办 APIO 了。在这个世界上有 $N$ 个国家，这些国家由 $0$ 到 $N − 1$ 标号，还有 $M$ 条双向道路（每条边双向都可以通行），这些道路由 $0$ 到 $M − 1$ 标号。每条道路连接两个不同的国家，$x[i]$ 和 $y[i]$，并需要花费时间 $c[i]$ 来通过该道路。除了你所在的国家的选手，所有选手都已经聚集在赛博乐园参加 API","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9370"},"statements":[{"statement_type":"Markdown","content":"3742 年已经到来，现在轮到赛博乐园主办 APIO 了。在这个世界上有 $N$ 个国家，这些国家由 $0$ 到 $N − 1$ 标号，还有 $M$ 条双向道路（每条边双向都可以通行），这些道路由 $0$ 到 $M − 1$ 标号。每条道路连接两个不同的国家，$x[i]$ 和 $y[i]$，并需要花费时间 $c[i]$ 来通过该道路。除了你所在的国家的选手，所有选手都已经聚集在赛博乐园参加 APIO 了。你生活在国家 $0$，而赛博乐园是国家 $H$。你作为你的国家最聪明的人，你的帮助刻不容缓。更具体地，你需要确定从你的国家到达赛博乐园所需的最少时间。\n\n在经过有些国家时，你可以清除你的当前总通过时间。此外，还有些国家在你经过他们时可以将你的当前总通过时间除以 $2$（我们称之为“除以 $2$ 的能力”）。你可以重复经过一个国家。每次你经过一个国家时，你可以选择是否使用这个国家的特殊能力。但你每次经过一个国家时最多可以使用一次特殊能力（如果你多次经过一个国家，你每次经过都可以使用至多一次该国家的特殊能力）。此外，为了防止被赛博乐园化学基金会抓住，你最多只能使用“除以 $2$ 的能力”$K$ 次。一旦你到达赛博乐园，你就不能移动到其他任何地方，因为伟大的 APIO 竞赛即将开赛了！\n\n给出一个数组 $arr$ ，其中 $arr[i]$ 表示国家 $i (0 \\le i \\le N − 1)$ 的特殊能力。每个国家有下面 $3$ 种特殊能力之中的一种：\n\n - $arr[i] = 0$，意思是这个国家可以让当前总通过时间为 $0$。\n - $arr[i] = 1$，表示这个国家不会改变你的当前总通行时间。\n - $arr[i] = 2$，表示这个国家拥有让当前总通行时间除以 $2$ 的能力。\n\n保证 $arr[0] = arr[H] = 1$ 成立。换句话说，赛博乐园和你所在的国家没有任何特殊能力。\n\n你的国家不希望错过 APIO 的任何时刻，所以你需要找到到达赛博乐园的最短时间。如果你不能到达赛博乐园，你的答案应该是 $−1$。\n\n### 实现细节\n\n你需要实现以下函数：\n\n```cpp\ndouble 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```\n\n - $N$ : 国家的数量。\n - $M$ : 双向道路的数量。\n - $K$: “除以 $2$ 的能力”的最大使用次数。\n - $H$: 国家“赛博乐园”的标号。\n - $x, y, c$: 三个长度为 $M$ 的数组。三元组 $(x[i], y[i], c[i])$ 表示第 $i$ 条用来连接国家 $x[i]$ 和 $y[i]$ 的双向边，通过它的时间消耗是 $c[i]$。\n - $arr$: 一个长度为 $N$ 的数组。$arr[i]$ 表示国家 $i$ 的特殊能力。\n - 如果你能到达赛博乐园，调用该函数应返回从你的国家到达赛博乐园的最短时间，如果你不能，则返回 $−1$。\n - 这个过程可能会被多次调用。\n\n假设选手的答案为 $ans_1$ ，标准输出为 $ans_2$ ，当且仅当 $\\dfrac{|ans_1-ans_2|}{\\max\\{ans_2,1\\}} \\le 10 ^ {-6}$ 时你的输出被视为是正确的。\n\n注意：由于函数调用可能会发生多次，选手需要注意之前调用的残余数据对于后续调用的影响。\n\n## Input\n\n评测程序示例读取如下格式的输入：\n\n - 第 $1$ 行: $T$\n \n对于 $T$ 组测试数据中的每一个:\n - 第 $1$ 行: $N \\ M \\ K$\n - 第 $2$ 行: $H$\n - 第 $3$ 行: $arr[0] \\ arr[1] \\ arr[2] \\  \\cdots  \\ arr[N − 1]$\n - 第 $4 + i(0 \\le i \\le M − 1)$ 行: $x[i] \\ y[i]  \\ c[i]$\n\n## Output\n\n评测程序示例按照如下的格式打印你的答案：\n\n对于每组测试数据：\n\n- 第 $1$ 行: 调用 `solve` 的返回值\n\n[samples]\n\n## Background\n\n**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。**\n\n提交时，无需引用 `cyberland.h`。你提交的代码中需要实现以下函数：\n\n```cpp\ndouble 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```\n\n## Note\n\n### 例子\n\n#### 样例 1\n\n考虑下面的调用：\n\n```cpp\nsolve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});\n```\n\n唯一的到达赛博乐园的路径是 $0 \\rightarrow 2$，因为你到达了赛博乐园之后不能再移动到其他任何地方。通行时间的计算过程如下：\n\n| 国家编号 | 通行时间 |\n| :--: | :--: |\n| $0$ | $0$ |\n| $2$ | $0 + 4 \\rightarrow 4(\\text{求和}) \\rightarrow 4(\\text{特殊能力})$|\n\n#### 样例 2\n\n考虑下面的调用：\n\n```cpp\nsolve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});\n```\n\n从你的国家到赛博乐园有两条路径：$0 \\rightarrow 1 \\rightarrow 3$ 和 $0 \\rightarrow 2 \\rightarrow 3$。\n\n如果选择路径 $0 \\rightarrow 1 \\rightarrow 3$，通行时间的计算如下：\n\n| 国家编号 | 通行时间 |\n| :--: | :--: |\n| $0$ | $0$ |\n| $1$ | $0 + 5 \\rightarrow 5(\\text{求和}) \\rightarrow 0(\\text{特殊能力})$|\n| $3$ | $0 + 2 \\rightarrow 2(\\text{求和}) \\rightarrow 2(\\text{特殊能力})$|\n\n如果选择路径 $0 \\rightarrow 2 \\rightarrow 3$，通行时间的计算如下：\n\n| 国家编号 | 通行时间 |\n| :--: | :--: |\n| $0$ | $0$ |\n| $2$ | $0 + 4 \\rightarrow 4(\\text{求和}) \\rightarrow 2(\\text{特殊能力})$|\n| $3$ | $2 + 4 \\rightarrow 6(\\text{求和}) \\rightarrow 6(\\text{特殊能力})$|\n\n所以，上述调用应该返回 $2$。\n\n### 约束条件\n\n - $2 \\le N \\le 10^5 , \\sum N \\le 10^5$.\n - $0 ≤ M ≤ \\min\\{10^5, \\dfrac{N(N-1)}{2} \\}, \\sum M ≤ 10^5$.\n - $1 \\le K \\le 10^6$.\n - $1 \\le H < N$\n - $0 \\le  x[i], y[i] < N , x[i] \\neq y[i]$.\n - $1 \\le c[i] \\le 10^9$.\n - $arr[i] \\in \\{0, 1, 2\\}$.\n - 保证每两个国家之间至多使用一条道路进行连接。\n\n### 子任务\n\n1. (5 分)：$N \\le 3, K \\le 30$.\n2. (8 分)：$M = N − 1, K \\le 30, arr[i] = 1$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。\n3. (13 分)：$M = N − 1, K \\le 30, arr[i] \\in \\{0, 1\\}$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。\n4. (19 分)：$M = N − 1, K \\le 30, x[i] = i, y[i] = i + 1$.\n5. (7 分)：$K \\le 30, arr[i] = 1$.\n6. (16 分)：$K \\le 30, arr[i] \\in \\{0, 1\\}$.\n7. (29 分)：$K \\le 30$.\n8. (3 分)：没有特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9370","tags":["2023","APIO","交互题","Special Judge","O2优化"],"sample_group":[["3 2 30\n2\n1 2 1\n1 2 12\n2 0 4","4"],["4 4 30\n3\n1 0 2 1\n0 1 5\n0 2 4\n1 3 2\n2 3 4","2"]],"created_at":"2026-03-03 11:09:25"}}