アットウィキロゴ

[aoj]0072

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
 
#define INF 1<<30

struct node{
  int cost, num;
  node(int c, int n): cost(c), num(n){}
  bool operator >(const node &e) const{
	return cost > e.cost;
  }
 
};
 
int main(void){
  int n;
  int m;
  int n1,n2,c;
 
  while(1){
	cin >> n;
	if(n == 0) break;
 
	bool visited[n];
	memset(visited, false, sizeof(visited));
	int cost[n][n];
	fill((int *)cost, (int *)cost+n*n, INF);
	bool used[n];
	fill(used, used+n, false);
	priority_queue<node, vector<node>, greater<node> > q;
	int ret=0;
 
	cin >> m;
 
	for(int i=0;i<m;i++){
	  cin >> n1; cin.ignore();
	  cin >> n2; cin.ignore();
	  cin >> c;
 
	  cost[n1][n2] = c / 100 - 1;
	  cost[n2][n1] = c / 100 - 1;	
	}
	q.push(node(0,0));
	while(!q.empty()){
	  node tmp = q.top(); q.pop();
	  //cout << "poped: from " << tmp.num << " cost " << tmp.cost << endl;
 
	  if(used[tmp.num] == true) continue;
	  used[tmp.num] = true;
	  ret += tmp.cost;
 
	  for(int i=0;i<n;i++){
		if(cost[tmp.num][i] != INF){
		  q.push(node(cost[tmp.num][i], i));
		}
	  }
	}
	cout << ret << endl;
  }	
}
 
最終更新:2011年06月19日 00:33
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。