3742 年已经到来,现在轮到赛博乐园主办 APIO 了。在这个世界上有
在经过有些国家时,你可以清除你的当前总通过时间。此外,还有些国家在你经过他们时可以将你的当前总通过时间除以
给出一个数组
,意思是这个国家可以让当前总通过时间为 。 ,表示这个国家不会改变你的当前总通行时间。 ,表示这个国家拥有让当前总通行时间除以 的能力。
保证
你的国家不希望错过 APIO 的任何时刻,所以你需要找到到达赛博乐园的最短时间。如果你不能到达赛博乐园,你的答案应该是
实现细节
你需要实现以下函数:
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);
: 国家的数量。 : 双向道路的数量。 : “除以 的能力”的最大使用次数。 : 国家“赛博乐园”的标号。 : 三个长度为 的数组。三元组 表示第 条用来连接国家 和 的双向边,通过它的时间消耗是 。 : 一个长度为 的数组。 表示国家 的特殊能力。- 如果你能到达赛博乐园,调用该函数应返回从你的国家到达赛博乐园的最短时间,如果你不能,则返回
。 - 这个过程可能会被多次调用。
假设选手的答案为
注意:由于函数调用可能会发生多次,选手需要注意之前调用的残余数据对于后续调用的影响。
输入格式
评测程序示例读取如下格式的输入:
- 第
行:
对于
输出格式
评测程序示例按照如下的格式打印你的答案:
对于每组测试数据:
- 第
行: 调用solve
的返回值
样例 1
input
3 2 30 2 1 2 1 1 2 12 2 0 4
output
4
样例 2
input
4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4
output
2
提示
例子
样例 1
考虑下面的调用:
solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
唯一的到达赛博乐园的路径是
国家编号 | 通行时间 |
---|---|
样例 2
考虑下面的调用:
solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
从你的国家到赛博乐园有两条路径:
如果选择路径
国家编号 | 通行时间 |
---|---|
如果选择路径
国家编号 | 通行时间 |
---|---|
所以,上述调用应该返回
约束条件
. . . . . .- 保证每两个国家之间至多使用一条道路进行连接。
子任务
- (5 分):
. - (8 分):
,你可以通过这 条道路从任意国家到另外一个国家。 - (13 分):
,你可以通过这 条道路从任意国家到另外一个国家。 - (19 分):
. - (7 分):
. - (16 分):
. - (29 分):
. - (3 分):没有特殊限制。