UOJ Logo Universal Online Judge

UOJ

#843. 【APIO2023】赛博乐园

附件下载 统计

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

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

给出一个数组 arr ,其中 arr[i] 表示国家 i(0iN1) 的特殊能力。每个国家有下面 3 种特殊能力之中的一种:

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

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

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

实现细节

你需要实现以下函数:

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
  • 这个过程可能会被多次调用。

假设选手的答案为 ans1 ,标准输出为 ans2 ,当且仅当 |ans1ans2|max{ans2,1}106 时你的输出被视为是正确的。

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

输入格式

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

  • 1 行: T

对于 T 组测试数据中的每一个: - 第 1 行: N M K - 第 2 行: H - 第 3 行: arr[0] arr[1] arr[2]  arr[N1] - 第 4+i(0iM1) 行: x[i] y[i] c[i]

输出格式

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

对于每组测试数据:

  • 1 行: 调用 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});

唯一的到达赛博乐园的路径是 02,因为你到达了赛博乐园之后不能再移动到其他任何地方。通行时间的计算过程如下:

国家编号 通行时间
0 0
2 0+44(求和)4(特殊能力)
样例 2

考虑下面的调用:

solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});

从你的国家到赛博乐园有两条路径:013023

如果选择路径 013,通行时间的计算如下:

国家编号 通行时间
0 0
1 0+55(求和)0(特殊能力)
3 0+22(求和)2(特殊能力)

如果选择路径 023,通行时间的计算如下:

国家编号 通行时间
0 0
2 0+44(求和)2(特殊能力)
3 2+46(求和)6(特殊能力)

所以,上述调用应该返回 2

约束条件

  • 2N105,N105.
  • 0Mmin{105,N(N1)2},M105.
  • 1K106.
  • 1H<N
  • 0x[i],y[i]<N,x[i]y[i].
  • 1c[i]109.
  • arr[i]{0,1,2}.
  • 保证每两个国家之间至多使用一条道路进行连接。

子任务

  1. (5 分):N3,K30.
  2. (8 分):M=N1,K30,arr[i]=1,你可以通过这 M 条道路从任意国家到另外一个国家。
  3. (13 分):M=N1,K30,arr[i]{0,1},你可以通过这 M 条道路从任意国家到另外一个国家。
  4. (19 分):M=N1,K30,x[i]=i,y[i]=i+1.
  5. (7 分):K30,arr[i]=1.
  6. (16 分):K30,arr[i]{0,1}.
  7. (29 分):K30.
  8. (3 分):没有特殊限制。