#P8817. [CSP-S 2022] 假期计划

    ID: 148 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2022O2优化最短路CSP S 提高级

[CSP-S 2022] 假期计划

题目描述

小熊的地图上有 nn 个点,其中编号为 11 的是它的家、编号为 2,3,,n2, 3, \ldots, n 的都是景点。部分点对之间有双向直达的公交线路。如果点 xxz1z_1z1z_1z2z_2、……、zk1z_{k - 1}zkz_kzkz_kyy 之间均有直达的线路,那么我们称 xxyy 之间的行程可转车 kk 次通达;特别地,如果点 xxyy 之间有直达的线路,则称可转车 00 次通达。

很快就要放假了,小熊计划从家出发去 44不同的景点游玩,完成 55 段行程后回家:家 \to 景点 A \to 景点 B \to 景点 C \to 景点 D \to 家且每段行程最多转车 kk 次。转车时经过的点没有任何限制,既可以是家、也可以是景点,还可以重复经过相同的点。例如,在景点 A \to 景点 B 的这段行程中,转车时经过的点可以是家、也可以是景点 C,还可以是景点 D \to 家这段行程转车时经过的点。

假设每个景点都有一个分数,请帮小熊规划一个行程,使得小熊访问的四个不同景点的分数之和最大。

输入格式

第一行包含三个正整数 n,m,kn, m, k,分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 n1n - 1 个正整数,分别表示编号为 2,3,,n2, 3, \ldots, n 的景点的分数。

接下来 mm 行,每行包含两个正整数 x,yx, y,表示点 xxyy 之间有道路直接相连,保证 1x,yn1 \le x, y \le n,且没有重边,自环。

输出格式

输出一个正整数,表示小熊经过的 44 个不同景点的分数之和的最大值。

8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

27

7 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4

7

提示

【样例解释 #1】

当计划的行程为 1235711 \to 2 \to 3 \to 5 \to 7 \to 1 时,44 个景点的分数之和为 9+7+8+3=279 + 7 + 8 + 3 = 27,可以证明其为最大值。

行程 1357811 \to 3 \to 5 \to 7 \to 8 \to 1 的景点分数之和为 2424、行程 1328711 \to 3 \to 2 \to 8 \to 7 \to 1 的景点分数之和为 2525。它们都符合要求,但分数之和不是最大的。

行程 1235811 \to 2 \to 3 \to 5 \to 8 \to 1 的景点分数之和为 3030,但其中 585 \to 8 至少需要转车 22 次,因此不符合最多转车 k=1k = 1 次的要求。

行程 1232311 \to 2 \to 3 \to 2 \to 3 \to 1 的景点分数之和为 3232,但游玩的并非 44 个不同的景点,因此也不符合要求。

【样例 #3】

见附件中的 holiday/holiday3.inholiday/holiday3.ans

【数据范围】

对于所有数据,保证 5n25005 \le n \le 25001m100001 \le m \le 100000k1000 \le k \le 100,所有景点的分数 1si10181 \le s_i \le {10}^{18}。保证至少存在一组符合要求的行程。

测试点编号 nn \le mm \le kk \le
131 \sim 3 1010 2020 00
454 \sim 5 55
686 \sim 8 2020 5050 100100
9119 \sim 11 300300 10001000 00
121412 \sim 14 100100
151715 \sim 17 25002500 1000010000 00
182018 \sim 20 100100