Mạng lưới giao thông tiết kiệm

Buổi 73-74 — Virtual CF Graphs
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $n$ thành phố và $m$ tuyến đường hai chiều có thể xây dựng, tuyến thứ $i$ nối $u_i$ và $v_i$ với chi phí $w_i$. Hãy tìm tổng chi phí nhỏ nhất để xây dựng một tập hợp các tuyến đường sao cho từ bất kỳ thành phố nào cũng có thể đi đến mọi thành phố khác. Nếu không thể kết nối tất cả thành phố, in ra IMPOSSIBLE.

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$).
  • $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
  • Một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc IMPOSSIBLE.
Ví dụ
Input Output
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4
14
Giới hạn
  • $1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$
Draft saved