记录编号	581312	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.724 s
提交时间	2023-08-01 13:55:50	内存使用	7.22 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1510;
int n;
int a[N][N],d[N],ans;
bool v[N];
void prim(){
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    for(int i = 1;i < n;i++){
        int x = 0;
        for(int j = 1;j <= n;j++){
            if(!v[j] && (x == 0 || d[j] < d[x]))x = j;
        }
        v[x] = 1;
        for(int y = 1;y <= n;y++)
            if(!v[y])d[y] = min(d[y],a[x][y]);
    }
}
int main(){
    freopen("wire.in","r",stdin);
    freopen("wire.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    prim();
    for(int i = 1;i <= n;i++)ans += d[i];
    printf("%d\n",ans);
    
    return 0;
    
}