Cho đồ thị vô hướng
liên thông có trọng số G=(VG, EG), trong đó VG
là tập các đỉnh của G, EG là tập các cạnh của G. Đồ thị G có n đỉnh
và n-1 cạnh, các đỉnh được đánh số từ 1 đến n
Một đồ thị G’=(VG’,
EG’) được gọi là đồ thị con của G khi VG’⊆VG
và EG’ ⊆ EG.
Giá trị của một đồ thị
là tổng trọng số các cạnh trong đồ thị đó.
Cho tập X (X⊆VG)
gồm k
đỉnh. Hãy xác định đồ thị G’ liên thông có giá trị nhỏ nhất chứa tập X
Dữ liệu vào: Từ tệp
văn bản KAMP01.INP
+ Dòng đầu tiên ghi 2
số nguyên dương n và k (1≤K≤N≤500000)
+ n-1
dòng tiếp theo, mỗi dòng 3 số nguyên u, v, c cho biết c là trọng số của cạnh (u,v). (1≤u, v≤n; 1≤c≤106)
+ Tiếp theo gồm k
dòng, mỗi dòng ghi 1 số nguyên là số hiệu của đỉnh thuộc tập X
Dữ liệu ra: ghi vào tệp văn bản KAMP01.OUT
+ Một số nguyên duy
nhất là giá trị nhỏ nhất của G’
Ví dụ:
KAMP01.INP
|
KAMP01.OUT
|
KAMP01.INP
|
KAMP01.OUT
|
|
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
|
2
|
7
2
1
2 4
1
3 1
2 5
1
2
4 2
4
7 3
4
6 2
3
7
|
10
|
