「AOJ201~210」の編集履歴(バックアップ)一覧に戻る

AOJ201~210 - (2011/09/02 (金) 10:11:45) のソース

*0201 Wrought Gold Master
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201

解法
アイテムを一つずつ確かめて、連金で安くなるならその値段に改定します。
改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがも止まります。
非常に短いコードで実装してる方もいるのでもっと賢い方法があるかもしれません。



 #include<iostream>
 #include<map>
 #include<string>
 #include<vector>
 using namespace std;
 void setData(int n){	
	map<string,int> items;
	map<string,vector<string> > process;
	map<string,int>::iterator itemIt;
	vector<string>::iterator processIt,end;
	int Count=1,value,m,k,sum;
	string name,item;	
	for(int i=0;i<n;i++){
		std::cin>>name>>value;
		items[name]=value;
	}
	std::cin>>m;
	for(int i=0;i<m;i++){
		std::cin>>name>>k;
		for(int i=0;i<k;i++){
			cin>>item;
			process[name].push_back(item);
		}
	}
	cin>>name;
	while(Count>0){
		Count=0;
		itemIt=items.begin();
		while(itemIt!=items.end()){
			sum=0;
			if(process.find((*itemIt).first)!=process.end()){
				processIt=process[(*itemIt).first].begin();
				end=process[(*itemIt).first].end();
				while(processIt!=end){
					sum+=items[*processIt];
					processIt++;
				}
				if(sum<(*itemIt).second){
					items[(*itemIt).first]=sum;
					Count++;
				}
			}
			itemIt++;
		}
	}
	cout<<items[name]<<"\n";
 }
 int main(){
	int n;
	while(scanf("%d",&n),n>0){
		setData(n);
	}
 }