Thuật toán Prim xây cây khung nhỏ nhất bằng cách bắt đầu từ một đỉnh và liên tục thêm cạnh nhẹ nhất nối cây hiện tại với một đỉnh mới (dùng hàng đợi ưu tiên). Kết quả tổng trọng số trùng với Kruskal.
Cho đồ thị vô hướng liên thông có trọng số, in tổng trọng số cây khung nhỏ nhất (bắt đầu từ đỉnh 1).
Dòng đầu n m. m dòng u v w. Đồ thị liên thông.
1 <= n <= 1000; n-1 <= m <= 5000; 1 <= w <= 10^6.
Một số nguyên: tổng trọng số cây khung nhỏ nhất.
Ví dụ:
Đầu vào:
4 5
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
Đầu ra:
6
Giải thích:
Đang tải editor...