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

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 galaxies connected by N - 1 wormholes! Wormhole i connects galaxies a_i and b_i and takes 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 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?


1 \le K \le N - 1
1 \le s_i \le N - 1
1 \le a_i, b_i \le N
1 \le t_i \le 1\,000

Subtask 1 [20%]

2 \le N \le 20

Subtask 2 [20%]

2 \le N \le 2\,000

Subtask 3 [60%]

2 \le N \le 200\,000

Input Specification

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

Output Specification

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

Sample Input 1

5 1
1 4 5
4 3 3
4 2 2
3 5 1

Sample Output 1


Explanation for Sample 1

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

Sample Input 2

5 4
1 2 3 4
1 4 5
4 3 3
4 2 2
3 5 1

Sample Output 2