| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 67 | 43 | 35 | 67.308% |
Lilith is a hungry caterpillar! From her vantage point at the root of a tree, she has identified some leaves she wishes to munch before returning to the root. She wants to finish munching all of them as quickly as possible so that she will grow into a plump, buttery butterfly.
The tree Lilith occupies is a bit unusual. We can view it as a collection of nodes, where some of the nodes contain leaves that Lilith wishes to munch. Each branch connects exactly two nodes together. It is guaranteed that between every pair of nodes, there is precisely one way to travel from one to the other.
Given a description of the tree and which nodes have leaves that Lilith wishes to munch, can you help Lilith route her munching by minimizing the time she must travel?
Figure 1: Illustration of Sample Input 1ドル$. Lilith can munch the nodes at leaves 2,3,6ドル$ and return to the root 0ドル$ by following the following sequence of nodes: 0ドル→4→6→4→0→1→2→1→3→1→0$. The total distance Lilith travels is the length of each branch she crossed in this sequence: 2ドル+3+たす3+たす2+たす5+たす1+たす1+たす4+たす4+たす5=わ30$.
The first line of input contains two integers $N$ (1ドル≤N≤1000$), which is the number of nodes in the tree, and $K$ (1ドル≤K≤N$), which is the number of leaves to be munched.
The next $N-1$ lines of input describe the branches (edges) of the tree. The $i$th such line contains three integers $s_i,ドル $t_i$ (0ドル≤s_i,t_i<N,ドル $s_i≠t_i$), and $d_i$ (0ドル≤d_i≤10^6$). This indicates there is a branch between node $s_i$ and node $t_i$ which takes $d_i$ time to cross. Furthermore, if we view the tree as rooted at node 0ドル,ドル we have that $s_i$ is the parent of $t_i$ (i.e. $s_i$ lies on the unique path from 0ドル$ to $t_i$). Lilith always starts at the root node 0ドル$.
The last line of input contains $K$ distinct integers $a_1,\dots ,a_K$ (0ドル≤a_i<N$), which indicates the nodes containing leaves that Lilith wants to munch.
Display the length of the shortest path along the branches of the tree, starting and ending at the root, which allows Lilith to eat all leaves.
7 3 0 1 5 0 4 2 1 2 1 1 3 4 4 5 3 4 6 3 2 3 6
30
6 3 0 1 5 1 2 5 2 3 42 2 4 347 2 5 612 3 4 5
2022
3 2 0 1 0 0 2 21 1 2
42
University > University of Alberta Programming Contest > UAPC 2022 > Division 1 J번
University > University of Alberta Programming Contest > UAPC 2022 > Division 2 J번