AOJ_0201 Wrought Gold Master
問題
解法
STLゲー。mapをアイテムの値段用とレシピ用に2つ使う。
再帰で最小の金額を求めていく。
#include <cstdio> #include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; typedef map<string, int> ITEM; typedef map<string, vector<string> > RECIPE; ITEM item; RECIPE recipe; int solve(string it){ int ans = 0; vector<string> v; v = recipe[it]; if(v.size() == 0) return item[it]; for(int i = 0; i < v.size(); i++){ ans += solve(v[i]); } return min(ans, item[it]); } int main(){ int n, m; string name; while(scanf("%d", &n) && n){ item.clear(); recipe.clear(); for(int i = 0; i < n; i++){ int p; cin >> name >> p; item.insert(ITEM::value_type(name, p)); } scanf("%d", &m); for(int i = 0; i < m; i++){ int l; vector<string> v; cin >> name >> l; for(int j = 0; j < l; j++){ string s; cin >> s; v.push_back(s); } recipe.insert(RECIPE::value_type(name, v)); } cin >> name; printf("%d\n", solve(name)); } return 0; }
記念の(2^7)AC
問題数順位も199位になりました。