DMOPC '18 Contest 4 P5 - Dr. Henri and Wormholes

Points: 25 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

Problem types

Dr. Henri has recently been studying wormholes, tunnels in the fabric of spacetime. A wormhole connects two different galaxies, may be traversed in either direction, and allows one to travel between the two galaxies in mere minutes. Wormholes are very rare and contain all sorts of exotic matter.

One day, Dr. Henri and his team discover a cluster of $N$ $N$ galaxies connected by $N - 1$ $N - 1$ wormholes! Wormhole $i$ $i$ connects galaxies $a_i$ $a_{i}$ and $b_i$ $b_{i}$ and takes $t_i$ $t_{i}$ minutes to traverse. Dr. Henri notes that it is possible to travel from any galaxy to any other galaxy in the cluster using wormholes.

As Dr. Henri and his team are very interested in exotic matter, they plan to dispatch a space probe into the galaxy cluster to investigate. They want to choose a path through the cluster so that the probe spends the longest time possible travelling through wormholes. That way, it can collect the most data. The path can start at any galaxy and end at any galaxy they choose.

Unfortunately, a typical wormhole can only be used once; sending even a small probe through one expends so much energy that the wormhole evaporates and cannot be used again. However, Dr. Henri has noticed that exactly $K$ $K$ of the wormholes in the cluster are supermassive wormholes. These powerful wormholes can be used up to two times before they evaporate.

What is the largest amount of time the probe can spend in transit?

Constraints

$1 \le K \le N - 1$ $1 \leq K \leq N - 1$
$1 \le s_i \le N - 1$ $1 \leq s_{i} \leq N - 1$
$1 \le a_i, b_i \le N$ $1 \leq a_{i}, b_{i} \leq N$
$1 \le t_i \le 1\,000$ $1 \leq t_{i} \leq 1 000$

Subtask 1 [20%]

$2 \le N \le 20$ $2 \leq N \leq 20$

Subtask 2 [20%]

$2 \le N \le 2\,000$ $2 \leq N \leq 2 000$

Subtask 3 [60%]

$2 \le N \le 200\,000$ $2 \leq N \leq 200 000$

Input Specification

The first line of input will contain two space-separated integers, $N$ $N$ and $K$ $K$ .
The next line will contain $K$ $K$ space-separated integers, $s_1, s_2, \dots, s_K$ $s_{1}, s_{2}, \dots, s_{K}$ , the indices of the supermassive wormholes.
The next $N - 1$ $N - 1$ lines will each contain three space-separated integers, $a_i$ $a_{i}$ , $b_i$ $b_{i}$ , and $t_i$ $t_{i}$ , the description of the $i$ $i$ -th wormhole.

Output Specification

The longest possible time the space probe can spend travelling through wormholes, in minutes.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample 1

The optimal path is through the galaxies 1 -> 4 -> 3 -> 4 -> 2.

Sample Input 2

Copy

Sample Output 2

Copy

Comments

There are no comments at the moment.