https://vjudge.net/contest/363991#problem/C

#include 
#include 
#include 
#include 
#include 
#include #define inf 2147483647
#define N 1000010
#define p(a) putchar(a)
#define For(i,a,b) for(long long i=a;iusing namespace std;
long long n,cnt,x,ans,y;
long long d[N];
struct tree{
    long long l;
    long long r;
    long long v;
    bool operator const tree &x) const{
        return vx.v;
    }
}e[N];

void in(long long &x){
    long long y=1;char c=getchar();x=0;
    while(c‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
    while(c‘9‘&&c>=‘0‘){ x=(x1)+(x3)+c-‘0‘;c=getchar();}
    x*=y;
}
void o(long long x){
    if(x0){p(‘-‘);x=-x;}
    if(x>9)o(x/10);
    p(x%10+‘0‘);
}

long long find(long long x){
    if(d[x]==x) return x;
    return d[x]=find(d[x]);
}

signed main(){
    in(n);
    For(i,1,n) d[i]=i;
    For(i,1,n){
        in(x);
        e[++cnt].l=0;
        e[cnt].r=i;
        e[cnt].v=x;
    }
    For(i,1,n)
        For(j,1,n){
            in(x);
            if(ij){
                e[++cnt].l=i;
                e[cnt].r=j;
                e[cnt].v=x;
            }
        }
    sort(e+1,e+cnt+1);
    For(i,1,cnt){
        x=find(e[i].l);
        y=find(e[i].r);
        if(x!=y){
            ans+=e[i].v;
            d[x]=y;
        }
    }
    o(ans);
    return 0;
}