SRM433 div2 hard
愚直にレシピをn^2回更新すればよい。
#include <iostream> #include <map> #include <sstream> #include <string> #include <vector> typedef long long LL; using namespace std; class MakingPotions { public: int getCost(vector <string> marketGoods, vector <int> cost, vector <string> recipes) { int n=recipes.size(); map<string,LL> ans; vector<string> result(n); vector<vector<string> > ingredient(n,vector<string>(0)); vector<vector<LL> > amount(n,vector<LL>(0)); for(int i=0;i<(int)marketGoods.size();i++) ans[marketGoods[i]]=cost[i]; for(int i=0;i<n;i++) { for(int j=0;j<recipes[i].size();j++) { char c=recipes[i][j]; recipes[i][j]=(c=='=' || c=='+')?' ':c; } string s; int a; stringstream ss(recipes[i]); ss >> result[i]; cout << result[i]; while(ss >> a >> s) { cout << " " << a << " " << s; amount[i].push_back(a); ingredient[i].push_back(s); } cout << endl; } for(int time=0;time<n;time++) for(int i=0;i<n;i++) { bool b=true; for(int j=0;j<(int)ingredient[i].size();j++) if(ans.find(ingredient[i][j])==ans.end()) b=false; if(!b) continue; LL a=0; for(int j=0;j<(int)ingredient[i].size();j++) a=min((LL)1000000001,a+amount[i][j]*ans[ingredient[i][j]]); if(ans.find(result[i])!=ans.end()) ans[result[i]]=min(ans[result[i]],a); else ans[result[i]]=min((LL)1000000001,a); cout << "a=" << a << endl; } return (int)(ans.find("LOVE")!=ans.end())?ans["LOVE"]:-1; } };