Mạng lưới trạm phát điện
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ thành phố cần được cấp điện. Để thành phố $i$ có điện, hoặc là xây dựng một trạm phát điện trực tiếp tại thành phố $i$ với chi phí $c_i$, hoặc là nối dây điện từ thành phố $i$ đến một thành phố đã có điện (trực tiếp hoặc gián tiếp).
Có $M$ đường dây nối khả dĩ giữa các cặp thành phố $(u, v)$ với chi phí $w$. Hãy tìm tổng chi phí nhỏ nhất để tất cả $N$ thành phố đều có điện.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^9$).
- $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, 1 \le w \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 2 5 10 10 1 2 3 2 3 4 |
12 |
Giới hạn
- $1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$
Community Discussion