AOJ - Problem 0072 : Carden Lantern

• 問題文

史跡と史跡の間に灯篭を100m間隔でおき、すべての史跡がつながるようにしたとき、必要最小限の灯篭の数を求める問題です。

灯篭の数をコストと考え、史跡と史跡の間に灯篭をおくとき((史跡と史跡の距離)-100)/100が必要なコスト(灯篭の数)となります。すべての史跡がつながるようにしつつ最小のコストを求めるので最小全域木を求める問題となっています。最小全域木を求めるアルゴリズムで有名なもののひとつにプリム法というものがあります。今回はプリム法を使って解を求めました。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n, m;

const int INF = 1e+9;
const int MAX_V = 100;
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];

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

// 文字列sを文字c区切りで分割して返す
vector<string> split_string(string s, char c){
	string str;
	vector<string> vs;
	s.push_back( c );
	
	for(int i=0 ; i < s.size() ; i++ ){
		if( s[i] == c ){
			if( !str.empty() ){
				vs.push_back( str );
				str.clear();
			}
		}else{
			str.push_back( s[i] );
		}
	}
	return vs;
}

// stringをintに変換
int s_to_i(string s){
	int n=0;
	for(int i=0 ; i < s.size() ; i++ ){
		n *= 10;
		n += s[i] - '0';
	}
	return n;
}

int main(){
	while( cin >> n , n ){
		for(int u=0 ; u < n ; u++ ){
			for(int v=0 ; v < n ; v++ ){
				cost[u][v] = cost[v][u] = INF;
			}
		}
		
		cin >> m;
		cin.ignore();
		for(int i=0 ; i < m ; i++ ){
			string s;
			getline(cin,s);
			vector<string> vs = split_string( s , ',' );
			int u = s_to_i( vs[0] );
			int v = s_to_i( vs[1] );
			int c = (s_to_i( vs[2] ) - 100) / 100;
			cost[u][v] = cost[v][u] = c;
		}
		int ans = prim();
		cout << ans << endl;
	}
}