Prim

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct arista
{
    int desde, hacia, costo;
};

bool operator<(const arista &a, const arista &b)
{
    return a.costo > b.costo;
}

vector <vector <arista> > ady;

vector <arista> Prim(int cantNodos)
{
    vector <arista> arbol;
    vector <bool> enArbol(cantNodos+1, false);
    priority_queue <arista> pq;

    ///Meto las aristas del nodo 1
    for(int i=0; i<ady[1].size(); i++)
        pq.push(ady[1][i]);

    enArbol[1] = true;

    while(arbol.size() < cantNodos-1)
    {
        arista a = pq.top();
        pq.pop();

        if(enArbol[a.hacia] == true) ///Evito formación de ciclos
            continue;

        ///a.desde ya forma parte del arbol,
        ///porque si así no lo fuera, sería imposible
        ///que procecemos esta arista

        int nodo = a.hacia;
        enArbol[a.hacia] = true;
        arbol.push_back(a);


        for(int i=0; i<ady[nodo].size(); i++)
        {
            int vecino = ady[nodo][i].hacia;
            if(enArbol[vecino] == false)
                pq.push(ady[nodo][i]);
        }
    }

    return arbol;
}

int main()
{
    int cantNodos, cantAristas;
    cin >> cantNodos >> cantAristas;

    ady.resize(cantNodos+1);

    for(int i=0; i<cantAristas; i++)
    {
        int desde, hacia, costo;
        cin >> desde >> hacia >> costo;
        ady[desde].push_back({desde, hacia, costo});
        ady[hacia].push_back({hacia, desde, costo});
    }

    vector <arista> resultado = Prim(cantNodos);

    int costoTotal = 0;

    cout << "El arbol cubridor minimo es: " << endl;

    for(int i=0; i<resultado.size(); i++)
    {
        cout << "(" << resultado[i].desde << ",";
        cout << resultado[i].hacia << ") -> " << resultado[i].costo << endl;
        costoTotal += resultado[i].costo;
    }

    cout << "El costo total es: " << costoTotal << endl;
    return 0;
}