最小全域木問題

問題

確定済みの頂点の中から最短ルートを見つけるのを繰り返すプログラムである

//プリム法 (計算量: O(|V|^2))
vector<vector<int>> G; 

struct Prim {
    const int INF = 1e9;
    int sum;              // 重みの総和
    int n;                // 頂点数
    vector<int> mincost;  // 既に確定した頂点からの最小コスト（確定済みから行けない時は INF）
    vector<bool> used;    // 既に確定したかどうか
    Prim(vector<vector<int>> const& Graph) {
        init(Graph); //最小全域木
    }
    void init(vector<vector<int>> const& Graph) {
        n = (int)Graph.size(); //頂点数
        mincost.assign(n, INF); //コスト
        used.assign(n, false); //確定済みか
        sum = 0;
        mincost[0] = 0;  // 始め頂点0からスタートさせる
        while (true) {
            int v = -1;
            for (int u = 0; u < n; u++) {  //未確定 && (最初 || 最小値)
                if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
            }
            if (v == -1) break;  //全頂点確定済み
            used[v] = true;
            sum += mincost[v];
            for (int u = 0; u < n; u++) {  // 確定した頂点から行ける頂点について、最小コストを更新
                if (Graph[v][u] != -1) //つながっているなら
                  mincost[u] = min(mincost[u], Graph[v][u]);
            }
        }
    }
};

int main() {
    int n;
    cin >> n; // 頂点数
    G.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {//(i==jの時は-1)
            cin >> G[i][j]; //重み
        }
    }
    Prim prim(G);
    cout << prim.sum << endl;
    return 0;
}