Kết nối từ ma trận chi phí

Bối cảnh và bài toán

Một hệ thống gồm n trạm, giữa mọi cặp trạm đều có chi phí kéo cáp đã biết trong ma trận đối xứng.

Yêu cầu

Tính tổng chi phí nhỏ nhất để kết nối toàn bộ trạm.

Input

Dòng đầu n; tiếp theo n dòng, mỗi dòng n số w[i][j], với w[i][i]=0 và w[i][j]=w[j][i].

Output

In chi phí MST.

Ràng buộc

• 1 <= n <= 2000
• 0 <= w[i][j] <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 100 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4
0 1 4 3
1 0 2 5
4 2 0 1
3 5 1 0

Output

4

Giải thích. Prim duy trì chi phí nhỏ nhất để kéo mỗi đỉnh chưa chọn vào cây hiện tại.

Ví dụ 2

Input

2
0 7
7 0

Output

7

Giải thích. Prim duy trì chi phí nhỏ nhất để kéo mỗi đỉnh chưa chọn vào cây hiện tại.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.