AOJ:0180 Stellar Performance of the Debunkey Family

プリム法です。

#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int path[101][101];

int main(){
	string str;
	int n,m;
	while(~scanf("%d %d",&n,&m)){
		if(n==m && m==0) continue;
		
		int* mincost = new int[n];
		bool* used = new bool[n];

		fill((bool*)used,(bool*)used + n,false);
		fill((int*)mincost,(int*)mincost+n,INF);
		fill((int*)path,(int*)path+101*101,INF);

		for(int i=0;i<m;i++){
			int a,b,cost;
			scanf("%d %d %d",&a,&b,&cost);
			path[a][b] = min(cost,path[a][b]);
			path[b][a] = min(cost,path[b][a]);
		}

		int res=0;
		mincost[0] = 0;

		while(1){
			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];
			
			for(int u=0;u<n;u++){
				mincost[u] = min(mincost[u],path[v][u]);
			}
			
		}

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

		delete[] mincost;
		delete[] used;
	}
}