Mạng lưới kết nối tối thiểu (Steiner Tree)

Buổi 24 — Mock Contest Phase 1
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cạnh. Có $K$ đỉnh trọng yếu $T_1, T_2, \dots, T_K$.

Bạn cần chọn một tập con các cạnh sao cho tất cả $K$ đỉnh trọng yếu đều liên thông với nhau (có thể thông qua các đỉnh khác không nằm trong tập trọng yếu) và tổng trọng số các cạnh được chọn là nhỏ nhất.

Hãy tìm tổng trọng số nhỏ nhất đó, hoặc in ra -1 nếu không thể kết nối tất cả $K$ đỉnh trọng yếu.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, M, K$ ($1 \le N \le 100$, $0 \le M \le 500$, $1 \le K \le 10$).
  • Dòng thứ hai chứa $K$ số nguyên $T_1, T_2, \dots, T_K$ ($1 \le T_i \le N$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng trọng số nhỏ nhất, hoặc -1 nếu không thể kết nối.
Ví dụ
Input Output
5 6 3
1 3 5
1 2 4
2 3 4
2 4 1
4 5 2
1 5 10
3 5 10
11
4 2 2
1 4
1 2 5
3 4 5
-1
Giới hạn
  • $1 \le N \le 100$, $0 \le M \le 500$, $1 \le K \le 10$.
  • $1 \le w \le 10^9$.
Draft saved