Problem:


錬金マスター

  あなたはついに魔法の釜、錬金釜を手に入れました。錬金釜に複数のアイテムを入れると、新しいア イテムを作ることができます。新しく作ったアイテムは、他のアイテムを作るために錬金釜へ入れることもできます。アイテムを作るために必要なアイテムのリストを記したものを錬金レシピと呼ぶことにします。以下の 3 つは錬金レシピの例です。

     
 木片と糸でラケットができる。

     
 お米と水でおにぎりができる。

     
 ラケットとマイクとおにぎりでギターができる。

  アイテムはお金を使って手にいれることもできますが、錬金釜で作った方が安くすむ場合もあります。例えば、各アイテムの購入価格が以下のように与えられているとします。

アイテム名 購入価格(円)

   木片            3,000

   糸                800

   お米                36

   水                  0

   ラケット           5,000

   マイク            9,800

   おにぎり             140

   ギター           98,000

 ラケットは 5,000 円で購入できますが、木片と糸を購入して錬金すれば 3,800 円で手に入れられます。更に、錬金を重ねることによりとてもお得にアイテムを手に入れられます。図 1 は上記 3 つの錬金レシピ例を組み合わせたものです。ギターは 98,000 円で購入できますが、木片、糸、お米、水、マイクを購入して錬金すれば、たったの 13,636 円で手に入れられます。

図 1

 あなたは冒険を楽に進めるため、なるべく安く目的のアイテムを手に入れようと考えました。 アイテムのリスト、錬金レシピのリスト、指定されたアイテムを入力とし、指定されたアイテムを作るために必要な金額の最小値を出力するプログラムを作成して下さい。

n は 1 以上 100 以下の整数とし、各アイテムを購入する場合の値段 p は 0 以上 1000000 以下とします。アイテムの名前 i は 1 文字以上 100 文字以下のアルファベットからなる半角文字列です。錬金レシピの種類 m は 0 以上 100 以下の整数です。 1つの錬金レシピはアイテムの名前 o、それを作るために必要なアイテムの個数 k 、 k 個のアイテム名 q のリストによって与えられます。k は 100 以下とします。

-->

 各アイテムの数量に限りはないものとします。アイテムは複数のレシピに使われることがありますが、1 つのアイテムを作るためのレシピはたかだか 1 つです。また、あるアイテムを起点としてレシピをたどっていったとき、そのアイテムが再びレシピに現れることはありません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
s1 p1
s2 p2
:
sn pn
m
o1 k1 q1 q2 ... qk1
o2 k2 q1 q2 ... qk2
:
om km q1 q2 ... qkm
t

1 行目にリストに含まれるアイテムの種類数 n (1 ≤ n ≤ 100) が与えられます。続く n 行に i 番目のアイテムの名前 si (1 文字以上 100 文字以下のアルファベットからなる半角文字列) とそれを購入する場合の値段 pi (0 ≤ pi ≤ 1000000)が与えられます。

続く行に錬金レシピの数 m (0 ≤ m ≤ 100) が与えられます。続く m 行に i 番目のレシピの情報が与えられます。各レシピとして、アイテムの名前 oi、それを作るために必要なアイテムの個数 ki (1 ≤ ki ≤ 100) 、 ki 個のアイテム名 q1, q2 ... qki が与えられます。

最後の行に指定されたアイテム名 t が与えられます。

データセットの数は 30 を超えません。

Output

入力データセットごとに、最小の値段を１行に出力します。

Sample Input

8
wood 3000
string 800
rice 36
water 0
racket 5000
microphone 9800
onigiri 140
guitar 98000
3
racket 2 wood string
onigiri 2 rice water
guitar 3 racket microphone onigiri
guitar
1
computer 300000
0
computer
0

Output for the Sample Input

13636
300000



Sample input:
8
wood 3000
string 800
rice 36
water 0
racket 5000
microphone 9800
onigiri 140
guitar 98000
3
racket 2 wood string
onigiri 2 rice water
guitar 3 racket microphone onigiri
guitar
1
computer 300000
0
computer
0


Sample output:
13636
300000

Submission status: Wrong Answer

Solution code:
while True:

    item_list = {}

    n = int(input())
    if n == 0: break
    for _ in range(n):
        item, cost = input().split()
        item_list[item] = int(cost)

    recipe_list = {}

    k = int(input())
    for _ in range(k):
        material = input().split()
        items = material[2:]
        recipe_list[material[0]] = items

    t = input()

    item_cost = item_list[t]
    if k:
        recipe = recipe_list[t]

        recipe_cost = 0
        for item in recipe:
            if item in recipe_list:
                recipe_cost += sum([item_list[x] for x in recipe_list[item]])
            else:
                recipe_cost += item_list[item]
    
        if recipe_cost < item_cost:
            print(recipe_cost)
        else:
            print(item_cost)
    else:
        print(item_cost)

Submission status: Wrong Answer

Solution code:
def price(target, item, recipe):
    ret = [0]
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])

    return min(ret)

import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Wrong Answer

Solution code:
def price(target, item, recipe):
    ret = [0]
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])
    if len(ret) == 0:
        return 0

    return min(ret)

import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Wrong Answer

Solution code:
def price(target, item, recipe):
    ret = [0]
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])
    if len(ret) == 0:
        return 0

    return min(ret)

import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().strip().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Wrong Answer

Solution code:
def price(target, item, recipe):
    ret = [0]
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])

    return min(ret)

import sys
f = sys.stdin


while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().strip().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Wrong Answer

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        pricelist=[]
        recipedict={}
        costdict={}
        for i in range(n):
            [ii,p]=raw_input().split()
            pricelist.append([ii,int(p)])
            costdict[ii]=1000000000000
        pricelist.sort(key=lambda x:x[1])
        m=int(raw_input())
        for i in range(m):
            rec=raw_input().split()
            o=rec[0]
            k=int(rec[1])
            recipedict[o]=rec[2:]
        query=raw_input()
        while(1):
            cheapest=pricelist.pop(0)
            #if able to make
            if cheapest[0] in recipedict:
                priceifmade=0
                for reqitem in recipedict[cheapest[0]]:
                    priceifmade=priceifmade+costdict[reqitem]
                if priceifmade<cheapest[1]:
                    costdict[cheapest[0]]=priceifmade
                else:
                    costdict[cheapest[0]]=cheapest[1]
            else:
                costdict[cheapest[0]]=cheapest[1]
            if cheapest[0]==query:
                print costdict[cheapest[0]]
                break

Submission status: Wrong Answer

Solution code:
def check(item):
    price = 0
    for i in recipe[item[-1]]:
        if recipe.has_key(i) == False:
            price += pricelist[i]
        else:
            item.append(i)
            price += min(check(item), pricelist[item[-1]])
            item.pop()
    return price

while True:
    pricelist = {}
    recipe = {}

    n = input()
    if n == 0: break

    for i in range(n):
        item, price = raw_input().split()
        pricelist[item] = int(price)

    m = input()
    for i in range(m):
        data = raw_input().split()
        recipe[data[0]] = []
        for j in range(int(data[1])):
            recipe[data[0]].append(data[j + 2])

    if m == 0:
        print pricelist[raw_input()]
    else:
        price = check([raw_input()])
        print price

Submission status: Wrong Answer

Solution code:
def check(item):
    price = 0
    for i in recipe[item[-1]]:
        if recipe.has_key(i) == False:
            price += pricelist[i]
        else:
            item.append(i)
            price += min(check(item), pricelist[item[-1]])
            item.pop()
    return price

while True:
    pricelist = {}
    recipe = {}

    n = input()
    if n == 0: break

    for i in range(n):
        item, price = raw_input().split()
        pricelist[item] = int(price)

    m = input()
    for i in range(m):
        data = raw_input().split()
        recipe[data[0]] = []
        for j in range(int(data[1])):
            recipe[data[0]].append(data[j + 2])

    if m == 0:
        print str(pricelist[raw_input()])
    else:
        price = check([raw_input()])
        print str(price)

Submission status: Wrong Answer

Solution code:
while True:
  try:
    a=int(input())
    if a==0: break
    thing,money=[],[]
    for i in range(a):
      hoge=map(str,raw_input().split())
      thing.append(hoge[0])
      money.append(int(hoge[1]))
    a=int(input())
    if a==0:
      hoge=raw_input()
      print money[thing.index(hoge)]
    for i in range(a):
      hoge=map(str,raw_input().split())
      x,y=2,0
      for j in range(int(hoge[1])):
        y+=thing.index(hoge[x])
        x+=1
      else:
        if money[thing.index(hoge[0])]>y:
          money[thing.index(hoge[0])] = y
    else: 
      hoge=raw_input()
      try:
        print money[thing.index(hoge)]
      except ValueError: break
  except EOFError: break
  except ValueError: print 0

Submission status: Wrong Answer

Solution code:
while True:
 try:
  a= int(input())
  if a==0: break ;break
  else:
    t,m=[],[]
    for i in range(a):
      hoge=map(str,raw_input().split())
      t.append(hoge[0]) ; m.append(int(hoge[1]))
    a = int(input())
    if a==0:
      hoge=raw_input()
      if hoge not in t:
        print 0
        break
      else: print m[t.index(hoge)]
    for i in range(a):
      hoge=map(str,raw_input().split())
      if hoge[0] not in t: 
        print 0
        break
      qq=0
      for j in range(int(hoge[1])):
        qq+=m[t.index(hoge[j+2])]
      if qq < m[t.index(hoge[0])]:
        m[t.index(hoge[0])] = qq
    hoge =raw_input()
    if hoge not in t:
      print 0
      break
    else: print m[t.index(hoge)]
 except EOFError: break

Submission status: Accepted

Solution code:
def price(target, item, recipe):
    ret = []
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])
    if len(ret) == 0:
        return 0

    return min(ret)

import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().strip().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Accepted

Solution code:
while True:
	n = input()
	if n == 0: 
		break
	item = {}
	for n in range(n):
		name, cost = raw_input().split()
		item[name] = int(cost)
	for i in range(input()):
		recipe = raw_input().split()
		cost = sum(item[name] if name in item else 0 for name in recipe[2:])
		item[recipe[0]] = min(cost, item[recipe[0]])
	print item[raw_input()]

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        pricelist=[]
        recipedict={}
        costdict={}
        for i in range(n):
            [ii,p]=raw_input().split()
            pricelist.append([ii,int(p)])
            costdict[ii]=1000000000000
        pricelist.sort(key=lambda x:x[1])
        m=int(raw_input())
        for i in range(m):
            rec=raw_input().split()
            o=rec[0]
            k=int(rec[1])
            recipedict[o]=rec[2:]
        query=raw_input()
        while(1):
            cheapest=pricelist.pop(0)
            #if able to make
            if cheapest[0] in recipedict:
                priceifmade=0
                for reqitem in recipedict[cheapest[0]]:
                    priceifmade=priceifmade+costdict[reqitem]
                if priceifmade<cheapest[1]:
                    costdict[cheapest[0]]=priceifmade
                else:
                    costdict[cheapest[0]]=cheapest[1]
            else:
                costdict[cheapest[0]]=cheapest[1]
            for item in recipedict:
                priceifmade=0
                for reqitem in recipedict[item]:
                    priceifmade=priceifmade+costdict[reqitem]
                if priceifmade<costdict[item]:
                    costdict[item]=priceifmade
            if cheapest[0]==query:
                print costdict[cheapest[0]]
                break

Submission status: Accepted

Solution code:
def work(item):
    if recipe.has_key(item):
        price = 0
        for i in recipe[item]: price += work(i)
        p_list[item] = min(price, p_list[item])
        del recipe[item]
    return p_list[item]

while True:
    p_list = {}
    recipe = {}

    n = input()
    if n == 0: break

    for i in range(n):
        item, price = raw_input().split()
        p_list[item] = int(price)

    m = input()
    for i in range(m):
        data = raw_input().split()
        recipe[data[0]] = []
        for j in range(int(data[1])):
            recipe[data[0]].append(data[j + 2])

    if m == 0:
        print p_list[raw_input()]
    else:
        price = work(raw_input())
        print price

Submission status: Accepted

Solution code:
def f(target):
    total = 0
    for item in recipe[target]:
        if item in recipe:
            total += f(item)
        else:
            total += lis[item]
    else:
        if lis[target] < total:
            total = lis[target]
        return total

while True:
    N = int(raw_input())
    if N == 0: break
    lis = {}
    for n in range(N):
        i, p = raw_input().split()
        lis[i] = int(p)
    recipe = {}
    for m in range(int(raw_input())):
        line = raw_input().split()
        recipe[line[0]] = line[2:]
    target = raw_input()
    print f(target) if target in recipe else lis[target]

Submission status: Accepted

Solution code:
items = {}
recipes = {}


def reset():
    items.clear()
    recipes.clear()


def algorithm():
    while True:
        item_number = int(input())
        if item_number == 0:
            break
        reset()

        for _ in range(item_number):
            item, price = input().split()
            items[item] = int(price)

        recipe_number = int(input())
        for _ in range(recipe_number):
            recipe = input().split()
            r = []
            for i in range(int(recipe[1])):
                r.append(recipe[i + 2])
            recipes[recipe[0]] = r

        for _ in range(len(recipes)):
            for k, v in recipes.items():
                total = 0
                for i in range(len(v)):
                    total += items[v[i]]
                items[k] = items[k] if items[k] < total else total

        target = input()
        print(items[target])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
items = {}
recipes = {}


def reset():
    items.clear()
    recipes.clear()


def algorithm():
    while True:
        reset()

        for _ in range(int(input())):
            item, price = input().split()
            items[item] = int(price)

        if len(items) == 0:
            break

        for _ in range(int(input())):
            recipe = input().split()
            recipes[recipe[0]] = recipe[2:]

        for _ in range(len(recipes)):
            for k, v in recipes.items():
                total = 0
                for i in range(len(v)):
                    total += items[v[i]]
                items[k] = items[k] if items[k] < total else total

        print(items[input()])


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    buy = {}
    for i in xrange(n):
        s, p = raw_input().split()
        p = int(p)
        buy[s] = p
    m = input()
    make = {}
    for i in xrange(m):
        ipt = raw_input().split()
        o = ipt[0]
        q = ipt[2:]
        make[o] = q
    used = {}
    def dfs(s):
        if s in used:
            return used[s]
        if s in make:
            res = min(sum(dfs(t) for t in make[s]), buy[s])
        else:
            res = buy[s]
        used[s] = res
        return res
    print dfs(raw_input())

Submission status: Accepted

Solution code:
# Aizu Problem 0201: Wrought Gold Master
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

class DirectedGraph():
    def __init__(self):
        self.edges = {}

    def AddNode(self, node):
        if node not in self.edges:
            self.edges[node] = []

    def GetNodes(self):
        return list(self.edges.keys())

    def GetEdges(self):
        return self.edges

    def AddEdge(self, node1, node2):
        if node1 not in self.GetNodes():
            self.AddNode(node1)
        if node2 not in self.edges[node1]:
            self.edges[node1].append(node2)

    def RemoveEdge(self, node1, node2):
        if node1 not in self.edges or node2 not in self.edges[node1]:
            print("ERROR: can't remove edge", node1, "->", node2)
            print(self.edges)
            return
        self.edges[node1].remove(node2)

    def OutDegree(self, node):
        return len(self.edges[node])

    def InDegree(self, node):
        deg = 0
        for node2 in self.GetNodes():
            if node in self.GetNeighbors(node2):
                deg += 1
        return deg

    def GetNeighbors(self, node):
        return self.edges.get(node, [])
            
    def GetPath(self, source, target):
        # find path by BFS:
        predecessor = {node: -1 for node in self.GetNodes()}
        predecessor[source] = 0
        visited = {node: False for node in self.GetNodes()}
        queue = [source]
        while len(queue) > 0:
            current = queue.pop(0)
            visited[current] = True
            for neighbor in self.GetNeighbors(current):
                if not visited[neighbor] and neighbor not in queue:
                    queue.append(neighbor)
                    predecessor[neighbor] = current
                if neighbor == target:
                    queue = []
                    break
        # build path from predecessor info:
        if predecessor[target] == -1:
            return []
        path = [target]
        while path[0] != source:
            path = [predecessor[path[0]]] + path[:]
        return path

    def TopologicalSort(self):
        # determine topological sorting of graph by Kahn's algorithm;
        # edges are removed by this algorithm
        L = []
        S = [node for node in self.GetNodes() if self.InDegree(node) == 0]
        while len(S) > 0:
            n = S.pop(0)
            L.append(n)
            for m in self.GetNeighbors(n)[:]:
                self.RemoveEdge(n, m)
                if self.InDegree(m) == 0:
                    S.append(m)
        for node in self.GetNodes():
            if self.edges[node] != []:
                print("ERROR: graph has cycle!", self.edges)
                return
        return L


while True:
    n = int(input())
    if n == 0:
        break
    G = DirectedGraph()
    prices = {}
    for _ in range(n):
        item, price = input().split()
        prices[item] = int(price)
    m = int(input())
    recipes = {}
    for _ in range(m):
        inp = input().split()
        item = inp[0]
        recipes[item] = inp[2:]
        for source in inp[2:]:
            G.AddEdge(item, source)
    target = input().strip()
    for item in G.TopologicalSort()[::-1]:
        if item in recipes:
            prices[item] = min(prices[item], sum([prices[source] for source in recipes[item]]))
    print(prices[target])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
#import pdb;pdb.set_trace()
    
if False:
    fh = open('vol2_0201.txt', 'r')
else:
    fh = sys.stdin
    
def input():
    return(fh.readline())

def tot(item, pr, rec):
    if item in rec:
        ret = min(pr[item], sum([tot(p,pr,rec) for p in rec[item]]))
    else:
        ret = pr[item]

    return(ret)
        
while True:
    pr={}
    rec={}
    n = int(input())
    if n==0:
        break
    for _ in range(n):
        v = input().strip().split()
        pr[v[0]] = int(v[1])
    m = int(input())
    for _ in range(m):
        v = input().strip().split()
        rec[v[0]] = v[2:]

    item=input().strip()
    #sys.exit()
    print(tot(item, pr, rec))

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break

  def_dic = {}
  for _ in range(n):
    s, p = input().split()
    def_dic[s] = int(p)
  
  m = int(input())
  com_dic = {}
  for _ in range(m):
    lst = input().split()
    com_dic[lst[0]] = lst[2:]
  
  price_dic = {}
  
  def get_price(t):
    if t in price_dic:
      return price_dic[t]
    if t not in com_dic:
      price_dic[t] = def_dic[t]
      return def_dic[t]
    
    x = 0
    for q in com_dic[t]:
      x += get_price(q)
    ret = min(x, def_dic[t])
    price_dic[t] = ret
    return ret
  
  print(get_price(input()))

Submission status: Accepted

Solution code:
# AOJ 0201: Wrought Gold Master
# Python3 2018.6.26 bal4u

INF = 0x7fffffff

def calc(t):
	ans = INF
	if len(mono[t][1]) > 0:
		ans = 0
		for i in mono[t][1]: ans += calc(i)
	return min(ans, mono[t][0])

while True:
	n = int(input())
	if n == 0: break
	mono = {}
	for i in range(n):
		s, p = input().split()
		mono[s] = (int(p), [])
	m = int(input())
	for i in range(m):
		a = input().split()
		s, p = a[0], INF
		if s in mono: p = mono[s][0]
		mono[s] = (p, a[2:])
	print(calc(input()))

Submission status: Accepted

Solution code:
while True:
  a=int(input()) ;m,t=[],[]
  if a==0: break
  for i in range(a):
    hoge=map(str,raw_input().split());t.append(hoge[0]);m.append(int(hoge[1]))
  b=int(input())
  if b==0:
    hage=raw_input()
    if hage not in t:
      print 0
    else:
      print m[t.index(hage)]
  else:
    for i in range(b):
      hage=map(str,raw_input().split()); k = int(hage[1]) ;qq=0
      for j in range(k):
        if hage[j+2] not in t: pass
        else:
          qq+= m[t.index(hage[j+2])]
      if m[t.index(hage[0])] > qq:
        m[t.index(hage[0])] = qq
    tt = raw_input()
    if tt not in t:
      print 0
    else:
      print m[t.index(tt)]

Submission status: Accepted

Solution code:
while True:
    things = {}
    count = input()
    if count == 0: break
    for i in range(count):
        fuga = raw_input().split()
        things[fuga[0]] = int(fuga[1])
    for i in range(input()):
        fuga = raw_input().split()
        money =0
        for j in range(int(fuga[1])):
            hoge = things[fuga[j+2]] if fuga[j+2] in things else 0
            money+= hoge
        things[fuga[0]] = things[fuga[0]] if money > things[fuga[0]] else money
    ans = raw_input()
    fin = things[ans] if ans in things else 0
    print fin

Submission status: Accepted

Solution code:
while True:
    things = {}
    count = input()
    if count == 0: break
    for i in range(count):
        fuga = raw_input().split()
        things[fuga[0]] = int(fuga[1])
    for i in range(input()):
        fuga = raw_input().split()
        money =0
        for j in range(int(fuga[1])):
            hoge = things[fuga[j+2]] if fuga[j+2] in things else 0
            money+= hoge
        things[fuga[0]] = things[fuga[0]] if money > things[fuga[0]] else money
    ans = raw_input()
    print "%s"%(things[ans] if ans in things else "0")

Submission status: Accepted

Solution code:
while True:
    things = {}
    count = input()
    if count == 0: break
    for i in range(count):
        fuga = raw_input().split()
        things[fuga[0]] = int(fuga[1])
    for i in range(input()):
        fuga = raw_input().split()
        money =0
        for j in range(int(fuga[1])):
            hoge = things[fuga[j+2]] if fuga[j+2] in things else 0
            money+= hoge
        things[fuga[0]] = things[fuga[0]] if money > things[fuga[0]] else money
    print things[raw_input()]

Submission status: Accepted

Solution code:
while True:
    ts = {}
    c = input()
    if c == 0: break
    for i in range(c):
        f = raw_input().split()
        ts[f[0]] = int(f[1])
    for i in range(input()):
        f = raw_input().split()
        m =0
        for j in range(int(f[1])):
            h = ts[f[j+2]] if f[j+2] in ts else 0
            m+= h
        ts[f[0]] = ts[f[0]] if m > ts[f[0]] else m
    print ts[raw_input()]

Submission status: Accepted

Solution code:
while True:
    ts={}
    c=input()
    if c==0: break
    for i in range(c):
        f=raw_input().split()
        ts[f[0]]=int(f[1])
    for i in range(input()):
        f=raw_input().split()
        m=0
        for j in range(int(f[1])):
            h=ts[f[j+2]] if f[j+2] in ts else 0
            m+=h
        q=ts[f[0]]
        ts[f[0]]=q if m > q else m
    print ts[raw_input()]

Submission status: Accepted

Solution code:
z=lambda:raw_input().split()
while True:
    t={}
    c=input()
    if c==0:break
    for i in range(c):
        f,q=z()
        t[f]=int(q)
    for i in range(input()):
        f=z()
        m=sum([t[j] if j in t else 0 for j in f[2:]])
        q=t[f[0]]
        t[f[0]]=q if m>q else m
    print t[raw_input()]

Submission status: Accepted

Solution code:
z,r,o=lambda:raw_input().split(),range,input
while 1: 
    t={}
    c=o()
    if c==0:break
    for i in r(c):
        f,q=z()
        t[f]=int(q)
    for i in r(o()):
        f=z()
        m=sum([t[j] if j in t else 0 for j in f[2:]])
        q=t[f[0]]
        t[f[0]]=q if m>q else m
    print t[raw_input()]

Submission status: Accepted

Solution code:
q,w,e=range,input,raw_input
while True:
  n=w()
  if n==0:break
  d={}
  for i in q(n):
    o=e().split()
    d[o[0]]=int(o[1])
  for j in q(w()):
    t=e().split()
    a=sum([d[i] if i in d else 0 for i in t[2:]])
    d[t[0]]=a if a<d[t[0]] else d[t[0]]
  print d[e()]

Submission status: Accepted

Solution code:
INF = 1 << 29
while True:
    n = input()
    if n == 0:
        break
    dic = {}
    for _ in xrange(n):
        name, cost = raw_input().split()
        dic[name] = int(cost)
    m = input()
    recipe = []
    for _ in xrange(m):
        data = raw_input().split()
        if data[1] <= 0:
            m -= 1
            continue
        recipe.append([data[0]]+data[2:])
    for _ in xrange(m):
        for i in xrange(m):
            dic[recipe[i][0]] = min(dic[recipe[i][0]] if recipe[i][0] in dic else INF, 
                                    sum(map(lambda x:dic[x] if x in dic else INF, recipe[i][1:])))
    print dic[raw_input()]

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	item = {}
	for i in range(n):
		name,cost = raw_input().split()
		item[name] = int(cost)
	for i in range(input()):
		recipe = raw_input().split()
		cost = sum(item[name] if name in item else 0 for name in recipe[2:])
		item[recipe[0]] = min(cost, item[recipe[0]])
	print item[raw_input()]

Submission status: Accepted

Solution code:
class Data:
    def __init__(self,n,p):
        self.name = str(n)
        self.price = int(p)
        self.recipe = []

    def minCost(self):
        if self.recipe == []:
            return self.price
        else:
            return min(self.price,
                       sum(list(map(lambda x: Data.minCost(index[x]), self.recipe))))
    def str(self):
        return "{}:{}:{}".format(self.name, self.price, self.recipe)

    
i_str = input()
n = int(i_str)
index = {}
while n != 0:
    for i in range(n):
        i_str = input()
        name,price = i_str.split()
        index[name] = Data(name,price)

    i_str = input()
    m = int(i_str)
    for i in range(m):
        i_str = input()
        data = i_str.split()    
        index[data[0]].recipe = data[2:]
            
    q = input()
    print(index[q].minCost())
       
    i_str = input()
    n = int(i_str)
    index = {}

Submission status: Accepted

Solution code:
while True:
  item_num = int(input())
  if item_num == 0:
    break

  price_dict = {}
  for _ in range(item_num):
    item, price = input().split()
    price_dict[item] = int(price)

  recipe_num = int(input())
  recipe_dict = {}
  for _ in range(recipe_num):
    recipe = input().split()
    recipe_dict[recipe[0]] = recipe[2:]

  result_dict = {}

  def get_price(item):
    if item in result_dict:
      return result_dict[item]
    if item not in recipe_dict:
      result_dict[item] = price_dict[item]
      return price_dict[item]

    price = 0
    for recipe_item in recipe_dict[item]:
      price += get_price(recipe_item)
    result = min(price, price_dict[item])
    result_dict[item] = result
    return result

  item = input()
  print(get_price(item))

Submission status: Accepted

Solution code:
# from pprint import pprint as pprint
import copy

def findrecipe(rec,ite,obj):
    # pprint(rec)
    # print("obj: ",obj)
    # print("=-")
    try:
        mat = rec[obj]
        rec2 = copy.copy(rec)
        del rec2[obj]
        price = min(ite[obj],sum([findrecipe(rec2,ite,m) for m in mat]))
        # print(price,obj)
        return price
    except:
        return ite[obj]

while(True):
    try:
        item = {}
        n = int(input())
        for _ in range(n):
            s,p = input().split()
            p = int(p)
            item[s] = p
        recipe = {}
        m = int(input())
        for _ in range(m):
            o,k,qs = input().split(" ",2)
            recipe[o] = qs.split()

        t = input()
        print(findrecipe(recipe,item,t))
    except:
        break

Submission status: Accepted

Solution code:
def get_price(name, prices, recipe):
    return min(prices[name],
               sum(get_price(_name, prices, recipe) for _name in recipe[name])
               if name in recipe else float("inf")
               )


while True:
    n = int(input())
    if not n:
        break
    prices, recipe = {}, {}
    for _ in [0]*n:
        s, p = input().split()
        prices[s] = int(p)
    for _ in [0]*int(input()):
        a = input().split()
        recipe[a[0]] = a[2:]

    print(get_price(input(), prices, recipe))

Submission status: Runtime Error

Solution code:
def price(target, item, recipe):
    ret = []
    
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])

    return min(ret)

import sys
f = sys.stdin

while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))

Submission status: Runtime Error

Solution code:
def price(target, item, recipe):
    ret = []
     
    if target in recipe:
        ret.append(sum(price(r,item, recipe) for r in recipe[target]))
    if target in item:
        ret.append(item[target])
 
    return min(ret)
 
import sys
f = sys.stdin
 
 
while True:
    n = int(f.readline())
    if n == 0:
        break
    item = [f.readline().split() for _ in range(n)]
    item = {name:int(price) for name, price in item}
    recipe = [f.readline().strip().split() for _ in range(int(f.readline()))]
    recipe = {r[0]:r[2:] for r in recipe}
    print(price(f.readline().strip(), item, recipe))