Cây Steiner tối thiểu

Buổi 20 — Cây khung nhỏ nhất Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nế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$
Draft saved