Mở rộng mạng lưới cáp quang
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ thành phố. Hiện đã có sẵn $K$ tuyến cáp quang nối trực tiếp một số cặp thành phố (chi phí sử dụng là $0$). Ngoài ra, có $M$ tuyến cáp quang tiềm năng có thể xây dựng thêm, tuyến thứ $i$ nối $u_i, v_i$ với chi phí $w_i$. Hãy tìm tổng chi phí nhỏ nhất để xây dựng thêm cáp quang sao cho cả $N$ thành phố đều liên thông với nhau. Nếu không thể làm cho tất cả liên thông, in ra -1.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, K, M$ ($1 \le N \le 10^5$, $0 \le K, M \le 2 \cdot 10^5$).
- $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ là một tuyến cáp đã có sẵ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$, $0 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là chi phí tối thiểu, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 1 2 2 3 5 3 4 2 1 3 10 |
7 |
| 4 1 1 1 2 3 4 5 |
-1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le K, M \le 2 \cdot 10^5$
- $0 \le w \le 10^9$
Community Discussion