Baekjoon #1368

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int uf[303];

int find(int x) {
    if(uf[x] < 0) return x;
    return uf[x] = find(uf[x]);
}

bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b)return false;
    uf[b] = a;
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; cin >> N;
    vector<tuple<ll, int, int>> w;
    for(int i=0;i<=N;i++) uf[i] = -1;
    for(int i=0;i<N;i++) {
        int x;cin >> x;
        w.emplace_back(x, i, N);
    }
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            int x; cin >> x;
            if(i >= j) continue;
            w.emplace_back(x, i, j);
        }
    }

    sort(w.begin(), w.end());
    ll answer = 0;
    for(auto &[W, a, b]: w) {
        if(merge(a, b)) answer += W;
    }
    cout << answer;

    return 0;
}

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
dig_costs = [int(input()) for _ in range(N)]
link_costs = [list(map(int, input().split())) for _ in range(N)]
parents = list(range(N + 1))

def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]

def union_set(a, b):
    parent_a = find_parent(a)
    parent_b = find_parent(b)
    if parent_a < parent_b:
        parents[parent_b] = parent_a
    else:
        parents[parent_a] = parent_b

edges = []
for i in range(N):
    for j in range(i + 1, N):
        heapq.heappush(edges, [link_costs[i][j], i+1, j+1])
    heapq.heappush(edges, [dig_costs[i], 0, i + 1])

link_cnt = 0
total = 0
while edges:
    if link_cnt == N:
        break
    cost, n1, n2 = heapq.heappop(edges)
    p_n1 = find_parent(n1)
    p_n2 = find_parent(n2)
    if p_n1 != p_n2:
        union_set(n1, n2)
        total += cost
        link_cnt += 1

print(total)