English · Original
Chinese · Translation
Formal · Original
The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities.
After exploring the map of Serbia for a while, the competitors came up with the following facts: the country has _V_ cities which are indexed with numbers from 1 to _V_, and there are _E_ bi-directional roads that connect the cites. Each road has a weight (the time needed to cross that road). There are _N_ teams at the Bubble Cup and the competitors came up with the following plan: each of the _N_ teams will start their journey in one of the _V_ cities, and some of the teams share the starting position.
They want to find the shortest time _T_, such that every team can move in these _T_ minutes, and the number of different cities they end up in is at least _K_ (because they will only get to know the cities they end up in). A team doesn't have to be on the move all the time, if they like it in a particular city, they can stay there and wait for the time to pass.
Please help the competitors to determine the shortest time _T_ so it's possible for them to end up in at least _K_ different cities or print _\-1_ if that is impossible no matter how they move.
Note that there can exist multiple roads between some cities.
## Input
The first line contains four integers: _V_, _E_, _N_ and _K_ (1 ≤ _V_ ≤ 600, 1 ≤ _E_ ≤ 20000, 1 ≤ _N_ ≤ _min_(_V_, 200), 1 ≤ _K_ ≤ _N_), number of cities, number of roads, number of teams and the smallest number of different cities they need to end up in, respectively.
The second line contains _N_ integers, the cities where the teams start their journey.
Next _E_ lines contain information about the roads in following format: _A__i_ _B__i_ _T__i_ (1 ≤ _A__i_, _B__i_ ≤ _V_, 1 ≤ _T__i_ ≤ 10000), which means that there is a road connecting cities _A__i_ and _B__i_, and you need _T__i_ minutes to cross that road.
## Output
Output a single integer that represents the minimal time the teams can move for, such that they end up in at least _K_ different cities or output _\-1_ if there is no solution.
If the solution exists, result will be no greater than 1731311.
[samples]
## Note
Three teams start from city 5, and two teams start from city 2. If they agree to move for 3 minutes, one possible situation would be the following: Two teams in city 2, one team in city 5, one team in city 3 , and one team in city 1. And we see that there are four different cities the teams end their journey at.
Bubble Cup X 的参赛者们在比赛结束后聚在一起，讨论了解东道国及其城市的最佳方式。
在研究了塞尔维亚的地图一段时间后，参赛者们得出了以下结论：该国有 #cf_span[V] 个城市，编号从 #cf_span[1] 到 #cf_span[V]，并有 #cf_span[E] 条双向道路连接这些城市。每条道路都有一个权重（通过该道路所需的时间）。Bubble Cup 上共有 #cf_span[N] 支队伍，参赛者们提出了以下计划：每支 #cf_span[N] 支队伍将从 #cf_span[V] 个城市中的一个出发，部分队伍共享相同的起点。
他们希望找到最短时间 #cf_span[T]，使得每支队伍都能在 #cf_span[T] 分钟内移动，并且最终到达的不同城市数量至少为 #cf_span[K]（因为他们只会了解最终到达的城市）。队伍不必一直移动，如果他们喜欢某个城市，可以留在那里等待时间流逝。
请帮助参赛者们确定最短时间 #cf_span[T]，使得他们能够最终到达至少 #cf_span[K] 个不同的城市；如果无论如何移动都无法实现，请输出 _-1_。
注意：某些城市之间可能存在多条道路。
第一行包含四个整数：#cf_span[V], #cf_span[E], #cf_span[N] 和 #cf_span[K]（1 ≤ V ≤ 600， 1 ≤ E ≤ 20000， 1 ≤ N ≤ min(V, 200)， 1 ≤ K ≤ N），分别表示城市数量、道路数量、队伍数量和所需到达的最少不同城市数量。
第二行包含 #cf_span[N] 个整数，表示每支队伍的起始城市。
接下来的 #cf_span[E] 行，每行包含三条信息：#cf_span[Ai Bi Ti]（1 ≤ Ai, Bi ≤ V， 1 ≤ Ti ≤ 10000），表示存在一条连接城市 #cf_span[Ai] 和 #cf_span[Bi] 的道路，通过该道路需要 #cf_span[Ti] 分钟。
请输出一个整数，表示队伍移动的最短时间，使得他们最终到达至少 #cf_span[K] 个不同的城市；如果无解，请输出 _-1_。
如果存在解，结果不会超过 #cf_span[1731311]。
三支队伍从城市 5 出发，两支队伍从城市 2 出发。如果他们同意移动 3 分钟，一种可能的情况是：两支队伍在城市 2，一支队伍在城市 5，一支队伍在城市 3，一支队伍在城市 1。此时，他们最终到达了四个不同的城市。
## Input
第一行包含四个整数：#cf_span[V], #cf_span[E], #cf_span[N] 和 #cf_span[K]（1 ≤ V ≤ 600， 1 ≤ E ≤ 20000， 1 ≤ N ≤ min(V, 200)， 1 ≤ K ≤ N），分别表示城市数量、道路数量、队伍数量和所需到达的最少不同城市数量。第二行包含 #cf_span[N] 个整数，表示每支队伍的起始城市。接下来的 #cf_span[E] 行，每行包含三条信息：#cf_span[Ai Bi Ti]（1 ≤ Ai, Bi ≤ V， 1 ≤ Ti ≤ 10000），表示存在一条连接城市 #cf_span[Ai] 和 #cf_span[Bi] 的道路，通过该道路需要 #cf_span[Ti] 分钟。
## Output
输出一个整数，表示队伍移动的最短时间，使得他们最终到达至少 #cf_span[K] 个不同的城市；如果无解，请输出 _-1_。如果存在解，结果不会超过 #cf_span[1731311]。
[samples]
## Note
三支队伍从城市 5 出发，两支队伍从城市 2 出发。如果他们同意移动 3 分钟，一种可能的情况是：两支队伍在城市 2，一支队伍在城市 5，一支队伍在城市 3，一支队伍在城市 1。此时，他们最终到达了四个不同的城市。
**Definitions**
Let $ V, E, N, K \in \mathbb{Z}^+ $ denote the number of cities, roads, teams, and minimum required distinct destination cities, respectively.
Let $ S = (s_1, s_2, \dots, s_N) \in \{1, \dots, V\}^N $ be the multiset of starting cities of the $ N $ teams.
Let $ G = (V, E, w) $ be an undirected weighted graph, where $ w: E \to \mathbb{Z}^+ $ assigns to each edge $ (u,v) $ a travel time $ t_{uv} $.
**Constraints**
1. $ 1 \le V \le 600 $, $ 1 \le E \le 20000 $, $ 1 \le N \le \min(V, 200) $, $ 1 \le K \le N $
2. $ 1 \le t_{uv} \le 10000 $ for each road $ (u,v) \in E $
3. Multiple edges between same pair of cities are allowed.
**Objective**
Compute the minimal time $ T \in \mathbb{R}_{\ge 0} $ such that, for each team $ i \in \{1, \dots, N\} $, there exists a destination city $ d_i \in \{1, \dots, V\} $ with $ \text{dist}(s_i, d_i) \le T $, and the set $ \{d_1, \dots, d_N\} $ contains at least $ K $ distinct cities.
If no such $ T $ exists, output $ -1 $.
**Note**
$ \text{dist}(u,v) $ denotes the shortest path distance between cities $ u $ and $ v $ in $ G $.
API Response (JSON)
{
"problem": {
"name": "D. Exploration plan",
"description": {
"content": "The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities. After exploring the map of Serbia for a while, the co",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF852D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The competitors of Bubble Cup X gathered after the competition and discussed what is the best way to get to know the host country and its cities.\n\nAfter exploring the map of Serbia for a while, the co...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Bubble Cup X 的参赛者们在比赛结束后聚在一起，讨论了解东道国及其城市的最佳方式。\n\n在研究了塞尔维亚的地图一段时间后，参赛者们得出了以下结论：该国有 #cf_span[V] 个城市，编号从 #cf_span[1] 到 #cf_span[V]，并有 #cf_span[E] 条双向道路连接这些城市。每条道路都有一个权重（通过该道路所需的时间）。Bubble Cup 上共有 #cf_span...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ V, E, N, K \\in \\mathbb{Z}^+ $ denote the number of cities, roads, teams, and minimum required distinct destination cities, respectively. \nLet $ S = (s_1, s_2, \\dots, s_N) \\in ...",
"is_translate": false,
"language": "Formal"
}
]
}