POJ-1287(Networking) Prim

POJ-1287

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = ;
const int INF = ;
int cost[MAXN][MAXN];
int lowcost[MAXN];
int visit[MAXN];
int n, m;

int prim(){
    memset(visit, , sizeof(visit));
    for(int i = ; i <= n; ++i) lowcost[i] = cost[][i];
    lowcost[] = ;
    visit[] = ;
    int res = ;
    for(int i = ; i <= n; ++i){
        int flag = -;
        int minc = INF;
        for(int j = ; j <= n; ++j){
            if(!visit[j] && lowcost[j] < minc){
                minc = lowcost[j];
                flag = j;
            }
        }
        if(flag == -) return -;
        visit[flag] = ;
        res += minc;
        for(int j = ; j <= n; ++j){
            if(!visit[j] && lowcost[j] > cost[flag][j]){
                lowcost[j] = cost[flag][j];
            }
        }
    }
    return res;
}

int main(){
    int u, v, w;

    while(scanf("%d", &n) != EOF && n){
        for(int i = ; i < MAXN; ++i)
            for(int j = ; j < MAXN; ++j) cost[i][j] = (i == j) ?  : INF;
        scanf("%d", &m);
        for(int i = ; i < m; ++i){
            scanf("%d%d%d", &u, &v, &w);
            if(cost[u][v] >= w){
                cost[u][v] = cost[v][u] = w;
            }
        }
        int t = prim();
        printf("%d\n", t);
    }
    return ;
}