Problem H
Forest Fruits
You stay in a cottage at a clearing in a forest. The forest consists of $V$ clearings and $E$ trails. Clearings are open spots where fruits may be found, and are numbered from $1$ to $V$. Your cottage is at clearing $1$. Trails connects two clearings. You ensure self sustainability by gathering fruits in the forest for food.
Through extensive reconnaissance, you learn that there are $C$ clearings containing exactly one batch of growing fruits. You also learn that fruits in this forest, once picked, will take $K$ days to grow before it is ready to be picked again. (A fruit picked on day $X$ is ready to be picked again on day $X + K$)
It is currently day $1$. Coincidentally, all $C$ clearings have one batch of fruits ready to be picked. From now until day $M$ inclusive, what is the minimum distance you have to walk per day in order to be able to gather at least one batch of fruits and return to your cottage every day?
Input
The first line of the input contains $5$ integers $V$ ($1 \leq V \leq 20\, 000$) $E$ ($1 \leq E \leq 100\, 000$) $C$ ($1 \leq C \leq V$) $K$ ($1 \leq K \leq 2\, 000\, 000\, 000$) and $M$ ($1 \leq M \leq 2\, 000\, 000\, 000$).
The following $E$ lines contains $3$ space-separated integers each, $u_ i\: v_ i\: w_ i$ ($1 \leq u_ i, v_ i \leq V$, $1 \leq w_ i \leq 1\, 000\, 000$) describing a trail that directly connects clearing $u$ to clearing $v$ directly with a length of $w$ unit distance. There are at most one trail directly connecting any two clearings, and no trail connects a clearing to itself. There could be clearings that cannot be reached from the cottage.
The last line of the input contains $C$ distinct space separated integers $f_1$ to $f_ C$ ($1 \leq f \leq V$), the clearings where fruits grow.
Output
Output a single value—the required answer. If it is impossible to gather at least one batch of fruits every day from day $1$ until day $M$, output $-1$ instead.
Subtasks
-
(25 Points): $C = 1, K = 1$
-
(25 Points): $C = M, K = M$
-
(30 Points): $1 \leq M \leq 100\, 000$
-
(20 Points): No additional constraint.
Sample Input Explanation
For sample $1$, there are $2$ clearings with fruits, one located at clearing $2$ ($1$ unit distance away from the cottage) and one located at clearing $3$ ($2$ unit distance away from the cottage). Suppose you pick the fruit at clearing $2$ on day $1$. The total distance traveled on this day is $2$ units- the distance from your cottage to clearing $2$ and back. On day $2$, the fruit at clearing $2$ has not grown back yet (it will be available for picking on day $3$), and you will have to walk to clearing $3$ for fruits. The furthest distance you have walked in a single day so far is $4$ units- the distance from the cottage to clearing $3$ and back. The answer is the same if you had instead picked the fruits at clearing $3$ first and then clearing $2$.
For sample $2$, the fruits at both clearings do not grow back in time.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 2 2 3 1 2 1 2 3 1 2 3 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 2 3 3 1 2 1 2 3 1 2 3 |
-1 |
