← 返回题目列表

Codeforces · 852/D

D. 勘探计划

中文机器翻译题面 查看原题

泡泡杯X的参赛者们在赛后聚集在一起,讨论什么是了解主办国及其城市的最佳方式。

经过对塞尔维亚地图一段时间的探索,参赛者们得出了以下事实:该国有 V 个城市,分别用 1 到 V 的数字进行索引,并且有 E 条双向道路连接这些城市。每条路都有一个权重(穿过该路所需的时间)。泡沫杯比赛共有 N 支队伍,参赛者们制定了如下计划:N 支队伍各在 V 个城市之一开始旅程,部分队伍共享起始位置。

他们想要找到最短的时间T,使得每个团队都可以在这T分钟内移动,并且他们最终到达的不同城市的数量至少为K(因为他们只会知道他们最终到达的城市)。团队不必一直在移动,如果他们喜欢某个特定的城市,他们可以呆在那里等待时间过去。

请帮助参赛者确定最短时间T,以便他们有可能最终到达至少K个不同的城市,如果无论他们如何移动都不可能,则打印-1。

请注意,某些城市之间可能存在多条道路。

输入

第一行包含四个整数:V、E、N 和 K(1 ≤ V ≤ 600、1 ≤ E ≤ 20000、1 ≤ N ≤ min(V, 200)、1 ≤ K ≤ N)、城市数量、道路数量、团队数量以及最终需要到达的不同城市的最小数量。

第二行包含N个整数,即队伍开始旅程的城市。

接下来的 E 行包含以下格式的道路信息:Ai Bi Ti (1 ≤ Ai, Bi ≤ V, 1 ≤ Ti ≤ 10000),这意味着有一条道路连接城市 Ai 和 Bi,穿过该道路需要 Ti 分钟。

输出

输出一个整数,表示团队可以移动的最短时间,这样他们最终会到达至少 K 个不同的城市,如果没有解决方案,则输出 -1。

如果解存在,结果将不大于 1731311。

示例

输入 #1

6 7 5 4
5 5 2 2 5
1 3 3
1 5 2
1 6 5
2 5 4
2 6 7
3 4 11
3 5 3

输出 #1

3

注意

三支队伍从城市 5 出发,两支队伍从城市 2 出发。如果他们同意移动 3 分钟,一种可能的情况是:城市 2 两支队伍,城市 5 一支队伍,城市 3 一支队伍,城市 1 一支队伍。我们看到队伍在四个不同的城市结束旅程。