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

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

AOJ201~210 - (2011/09/02 (金) 10:21:58) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

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