prim impelementation

prim.cpp

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

// first is vtx, second is weight
typedef vector< list< pair<int, int> > >  TGraph;

int prim(int root, const TGraph& graph)
{
    // NOTE first is weight, second is vtx
    set< pair<int, int> > q;
    vector<bool> visited(graph.size(), false);
    q.insert( make_pair(0, root) );
    // keys[v] - min weight of edge which connect vertex v to the spantree
    vector<int> keys(graph.size(), numeric_limits<int>::max());
    keys[root] = 0;

    for (int i = 0; i < graph.size(); ++i) {
        if (q.empty())
            cout << "AAAA\n";
        int u = q.begin()->second;
        visited[u] = true;
        q.erase(q.begin());
        
        for (auto v : graph[u]) {
            if (visited[v.first] == false  && v.second < keys[v.first]) {
                //cout << "\tv=" << v.first << " " << v.second <<"\n";
                q.erase(  make_pair(keys[v.first], v.first) );
                keys[v.first] = v.second;
                q.insert( make_pair(keys[v.first], v.first) );
            }
        }
    }
    //for_each(keys.begin(), keys.end(), [](int v) { cout << v << " ";});
    //cout << "\n";
    return accumulate(keys.begin(), keys.end(), 0);
}

int main(int, char**)
{
    int n, m;
    cin >> n >> m;
    
    TGraph adj(n);
    for (int i = 0; i < m; ++i) {
        int f,l,w;
        cin >> f >> l >> w;
        --f; --l;
        adj[f].push_back( make_pair(l, w) );
        adj[l].push_back( make_pair(f, w) );
    }
    int root;
    cin >> root;
    --root;

    cout << prim(root, adj);    

    return 0;
}