reduzindo_detalhes_em_um_mapa_Prim.cpp

#include <cstdio>

#define MAXN 1010
#define INF 999999999

#define min(A,B) ((A)<(B))?(A):(B)

//Globais-------------
int n,m;
int marcado[MAXN];
int grafo[MAXN][MAXN];
//--------------------

void prim(int v){
    marcado[v] = 1;

    while(1){
        int davez = -1, menor = INF;

        for(int i=1;i<=n;i++)
            if( grafo[v][i] < menor && !marcado[i] ){
                menor = grafo[v][i];
                davez = i;
            }

        if( davez == -1 ) break;

        marcado[davez] = 1;

        for(int i=1;i<=n;i++)
            if( !marcado[i] )
                grafo[v][i] = min(grafo[v][i],grafo[davez][i]);
    }
}

int main(){

    scanf("%d %d", &n,&m);

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) grafo[i][j] = INF;

    for(int i=1;i<=m;i++){
        int a,b,c;

        scanf("%d %d %d", &a,&b,&c);

        grafo[a][b] = grafo[b][a] = c;
    }

    prim(1);

    int soma = 0;
    for(int i=2;i<=n;i++) soma += grafo[1][i];

    printf("%d\n", soma);

    return 0;
}