Mạng lưới kết nối tối thiểu (Steiner Tree)
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
-1nế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$.
Community Discussion