oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

visiting Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

visiting.html

Problem Description

Gug is going visiting! In the town that Gug lives in, there are a total of N houses and N - 1 roads, and each road i connects houses Ai and Bi, taking Ci minutes to travel in either direction. It is guaranteed that it is possible to travel from each house to another directly or indirectly using these roads.

Gug needs to visit a total of K of these houses. The ith house that Gug needs to visit is house Vi, and Gug needs to visit all the houses in some order during the day. At the start of the day, Gug can choose any house to start at, and then must travel from house to house such that he reaches all the houses that he needs to visit at least once. Assuming it takes a negligible amount of time for Gug to do the actual visiting, and Gug can end the day at any house, what is the minimum amount of time required for Gug to complete his visits?

Input

The first line of input will contain two integers, N and K.

The second line of input will contain K integers, representing the array V. V will not contain any number twice.

The next N - 1 lines of input will contain three integers each, Ai, Bi and Ci.

Output

The output should contain one integer, the minimum amount of time, in minutes, Gug needs to complete his visiting.

Limits

For all subtasks: 1 ≤ Ci ≤ 109, 0 ≤ Ai, Bi, Vi < N.

Subtask 1 (17%): 2 ≤ K ≤ N ≤ 8.

Subtask 2 (20%): 2 ≤ K ≤ N ≤ 1000.

Subtask 3 (15%): 2 ≤ N ≤ 200000, K = 2.

Subtask 4 (22%): 2 ≤ K = N ≤ 200000.

Subtask 5 (26%): 2 ≤ K ≤ N ≤ 200000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

7 3
4 0 6
0 2 4
2 4 3
4 5 2
2 1 1
1 3 5
1 6 2

Sample Output 1

13

Explanation

Gug visits 0, 4 then 6.

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
117211s256MBMinimum
220411s256MBMinimum
315201s256MBMinimum
422201s256MBMinimum
5261011s256MBMinimum
6011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o visiting -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.