Byteland has N cities (numbered from to ) and N-1 bidirectional roads. It is guaranteed that there is a route from any city to any other city.↵
↵
Jeanie is a postal worker who must deliver Kletters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for K letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all K letters.↵
↵
Note: The letters can be delivered in any order.↵
↵
The first line contains two space-separated integers, N (the number of cities) and K (the number of letters), respectively.↵
The second line contains K space-separated integers describing the delivery city for each letter.↵
Each line i of the N-1 subsequent lines contains 3 space-separated integers describing a road as ui,vi,di , where di is the distance (length) of the bidirectional road between cities ui and vi.↵
↵
↵
↵
~~~~~↵
sample:↵
5 3↵
1 3 4↵
1 2 1↵
2 3 2↵
2 4 2↵
3 5 3↵
↵
output:↵
6↵
↵
path:3-2-1-2-4↵
~~~~~↵
↵
↵
↵
approach for this problem↵
↵
O(V+E) solution intended
↵
Jeanie is a postal worker who must deliver Kletters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for K letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all K letters.↵
↵
Note: The letters can be delivered in any order.↵
↵
The first line contains two space-separated integers, N (the number of cities) and K (the number of letters), respectively.↵
The second line contains K space-separated integers describing the delivery city for each letter.↵
Each line i of the N-1 subsequent lines contains 3 space-separated integers describing a road as ui,vi,di , where di is the distance (length) of the bidirectional road between cities ui and vi.↵
↵
↵
↵
~~~~~↵
sample:↵
5 3↵
1 3 4↵
1 2 1↵
2 3 2↵
2 4 2↵
3 5 3↵
↵
output:↵
6↵
↵
path:3-2-1-2-4↵
~~~~~↵
↵
↵
↵
approach for this problem↵
↵
O(V+E) solution intended
