Cây Steiner tối thiểu
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị vô hướng có trọng số gồm $N$ đỉnh, $M$ cạnh và một tập gồm $K$ đỉnh trọng yếu phân biệt $t_1, t_2, \dots, t_K$.
Hãy tìm tổng trọng số nhỏ nhất của một cây con trong đồ thị chứa tất cả $K$ đỉnh trọng yếu (cây có thể đi qua các đỉnh trung gian khác ngoài $K$ đỉnh đã cho). Nếu không thể kết nối tất cả $K$ đỉnh trọng yếu, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($1 \le N \le 50, 0 \le M \le 500, 1 \le K \le \min(N, 8)$).
- Dòng thứ hai chứa $K$ số nguyên phân biệt $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_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
Dữ liệu ra
- In ra tổng trọng số nhỏ nhất của cây Steiner, hoặc
-1nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 5 6 3 1 3 5 1 2 2 2 3 2 2 4 1 4 5 1 1 5 10 3 5 10 |
6 |
| 4 2 3 1 2 3 1 2 5 3 4 5 |
-1 |
Giới hạn
- $1 \le N \le 50$
- $0 \le M \le 500$
- $1 \le K \le \min(N, 8)$
- $1 \le w_i \le 10^9$
Community Discussion