AOJ 0180 - Stellar Performance of the Debunkey Family(Prim法)

タイトルがながい

#include<iostream>
#include<algorithm>

const int MAX_N = 100, MAX_M = 100, INF = 1 << 24;
int n, m;
int cost[MAX_N][MAX_N], mincost[MAX_N], used[MAX_N];

int prim(){
	std::fill(mincost, mincost+MAX_N, INF);
	std::fill(used, used+MAX_N, 0);

	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		for(int i=0;i<n;i++){
			if(!used[i] && (v == -1 || mincost[i] < mincost[v])){
				v = i;
			}
		}

		if(v == -1){
			break;
		}
		used[v] = 1;
		res += mincost[v];

		for(int i=0;i<n;i++){
			mincost[i] = std::min(mincost[i], cost[v][i]);
		}
	}

	return res;
}

int main(){
	while(std::cin >> n >> m, n){
		for(int i=0;i<MAX_N;i++){
			std::fill(cost[i], cost[i]+MAX_N, INF);
		}
		for(int i=0;i<m;i++){
			int a, b, c;
			std::cin >> a >> b >> c;
			cost[a][b] = c;
			cost[b][a] = c;
		}
		std::cout << prim() << std::endl;
	}
}