Phủ cạnh tối thiểu tập đỉnh đặc biệt

Buổi 33 — Bitmask DP & SOS DP
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một đồ thị vô hướng liên thông có trọng số gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cạnh. Có $K$ đỉnh đặc biệt $S_1, S_2, \dots, S_K$. Hãy chọn ra một tập hợp các cạnh trong đồ thị sao cho mỗi đỉnh đặc biệt đều có ít nhất một cạnh được chọn kề với nó, đồng thời tổng trọng số các cạnh được chọn là nhỏ nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, M, K$ ($2 \le N \le 50$, $N - 1 \le M \le 500$, $1 \le K \le \min(N, 16)$).
  • Dòng thứ hai chứa $K$ số nguyên phân biệt $S_1, S_2, \dots, S_K$ ($1 \le S_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$, $u \ne v$, $1 \le w \le 10^9$) biểu thị cạnh nối giữa $u$ và $v$ với trọng số $w$.
Dữ liệu ra
  • In ra tổng trọng số nhỏ nhất của tập cạnh phủ hết $K$ đỉnh đặc biệt.
Ví dụ
Input Output
4 4 2
1 3
1 2 2
2 3 2
1 4 10
3 4 10
4
4 4 2
1 3
1 2 1
2 3 100
3 4 1
1 4 100
2
Giới hạn
  • $2 \le N \le 50$, $1 \le K \le 16$
  • $1 \le w \le 10^9$
Draft saved