2093: 假期计划（holiday）
Description
小熊的地图上有 n 个点，其中编号为 1 的是它的家、编号为 2，3， . . .， n 的都是景 点。部分点对之间有双向直达的公交线路。如果点 x 与 z1 、z1 与 z2 、……、zk−1 与 zk 、 zk 与 y 之间均有直达的线路，那么我们称 x 与 y 之间的行程可转车 k 次通达；特别地， 如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。
很快就要放假了，小熊计划从家出发去 4 个不同的景点游玩，完成 5 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家且每段行程最多转车 k 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A → 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C， 还可以是景点D → 家这段行程转车时经过的点。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大
Input
从文件 holiday.in 中读入数据。
第一行包含 3 个正整数 n, m, k，分别表示地图上点的个数、双向直达的点对数量、 每段行程最多的转车次数。
第二行包含 n − 1 个正整数，分别表示编号为 2, 3, . . . , n 的景点的分数。
接下来 m 行，每行包含两个正整数 x, y，表示点 x 和 y 之间有道路直接相连，保证 1 ≤ x, y ≤ n，且没有重边，自环。
Output
输出到文件 holiday.out 中。
输出一个正整数，表示小熊经过的 4 个不同景点的分数之和的最大值。
Sample Input Copy
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
Sample Output Copy
27HINT
【样例 1 解释】
当计划的行程为 1 → 2 → 3 → 5 → 7 → 1 时，4 个景点的分数之和为 9+7+8+3 = 27， 可以证明其为最大值。
行程 1 → 3 → 5 → 7 → 8 → 1 的景点分数之和为 24、行程 1 → 3 → 2 → 8 → 7→ 1 的景点分数之和为 25。它们都符合要求，但分数之和不是最大的。
行程 1 → 2 → 3 → 5 → 8 → 1 的景点分数之和为 30，但其中 5 → 8 至少需要转车2 次，因此不符合最多转车 k = 1 次的要求。
行程 1 → 2 → 3 → 2 → 3 → 1 的景点分数之和为 32，但游玩的并非 4 个不同的景 点，因此也不符合要求。
【样例 2 输入】
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
【样例 2 输出】
7
【数据范围】
对于所有数据，保证 5 ≤ n ≤ 2500, 1 ≤ m ≤ 10000, 0 ≤ k ≤ 100, 所有景点的分数1 ≤ si ≤1018。保证至少存在一组符合要求的行程。
|
测试点编号 |
n ≤ |
m ≤ |
k ≤ |
|
1∼3 |
10 |
20 |
0 |
|
4∼5 |
5 |
||
|
6∼8 |
20 |
50 |
100 |
|
9 ∼ 11 |
300 |
1000 |
0 |
|
12 ∼ 14 |
100 |
||
|
15 ∼ 17 |
2500 |
10000 |
0 |
|
18 ∼ 20 |
100 |