Minimum time to deliver k letters

Revision en4, by _Aryan_, 2023-07-15 13:45:05

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English _Aryan_ 2023-07-15 13:45:05 26 Tiny change: ' problem\n\nO(V+E) solution intended' -> ' problem\n'
en3 English _Aryan_ 2023-07-15 12:16:36 20
en2 English _Aryan_ 2023-07-15 12:15:37 506
en1 English _Aryan_ 2023-07-15 11:33:03 594 Initial revision (published)