Phủ cạnh tối thiểu tập đỉnh đặc biệt
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion