※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

AOJ201~210 - (2011/09/02 (金) 10:11:45) の編集履歴(バックアップ)


0201 Wrought Gold Master


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



#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);
}
}