AOJ 0072 Carden Lantern

最小全域木

//AOJ0072
#include<iostream>
#include<cstdio>
#define INF 1000000
using namespace std;

int n,m;
int cost[100][100];
int mincost[100]; 
bool used[100];

int Prim(){
	for(int i = 0; i < n; i++){
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		for(int u = 0; u < n;u++){
			if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if(v == -1) break;
		used[v] = true;
		res += mincost[v] / 100;
		for(int u = 0; u < n; u++){
		mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}
	
int main(){
	while(scanf("%d",&n)){
	if(n == 0)break;
	scanf("%d", &m);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n;j++){
			cost[i][j] = INF;
		}
	}
	for(int i = 0; i < n; i++) cost[i][i] = 0;
	for(int i = 0; i < m; i++){
		int a,b,c;
		scanf("%d,%d,%d", &a,&b,&c);
		cost[a][b] = cost[b][a] = c;
	}
	printf("%d\n", Prim()-n+1);
	}
	return 0;
}