USACO-T040: Agri-net

/*
ID: mickyta1
TASK: agrinet
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 5;

int mat[N][N], dist[N], idx[N];

int main(){
    freopen("agrinet.in", "r", stdin);
    freopen("agrinet.out", "w", stdout);

    int nVertex;
    scanf("%d", &nVertex);
    dist[0] = 1e9;
    for(int u = 1; u <= nVertex; ++u){
        for(int v = 1; v <= nVertex; ++v){
            scanf("%d", &mat[u][v]);
        }
        dist[u] = 1e9;
        idx[u] = u;
    }
    int mst = 0;
    dist[1] = 0;
    for(int i = 0; i < nVertex; ++i){
        int u = 0;
        for(int j = 1; j <= nVertex - i; ++j){
            if(dist[j] < dist[u]){
                u = j;
            }
        }
        mst += dist[u];
        for(int v = 1; v <= nVertex - i; ++v){
            dist[v] = min(dist[v], mat[idx[u]][idx[v]]);
        }
        swap(idx[u], idx[nVertex - i]);
        swap(dist[u], dist[nVertex - i]);
    }
    cout << mst << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}