Aizu Online Judge 0201 Wrought Gold Master

■0201 Wrought Gold Master

DFS．あるアイテムについてそれ自身を買う，あるいはレシピを用いて錬金するという両手法を試し，最小を返す．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  HashMap<String, Integer> val;  
18.  HashMap<String, LinkedList<String>> recipe;  
19.  String item;  
20.   
21.  void run(){  
22.   for(;;){  
23.    val=new HashMap<String, Integer>();  
24.    recipe=new HashMap<String, LinkedList<String>>();  
25.    n=sc.nextInt();  
26.    if(n==0){  
27.     break;  
28.    }  
29.    for(int i=0; i<n; i++){  
30.     String s=sc.next();  
31.     int d=sc.nextInt();  
32.     val.put(s, d);  
33.    }  
34.    m=sc.nextInt();  
35.    for(int j=0; j<m; j++){  
36.     String s=sc.next();  
37.     int k=sc.nextInt();  
38.     LinkedList<String> list=new LinkedList<String>();  
39.     for(int i=0; i<k; i++){  
40.      String t=sc.next();  
41.      list.add(t);  
42.     }  
43.     recipe.put(s, list);  
44.    }  
45.    item=sc.next();  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   println(dfs(item)+"");  
52.  }  
53.   
54.  int dfs(String s){  
55.   int res=INF;  
56.   if(val.containsKey(s)){  
57.    res=min(res, val.get(s));  
58.   }  
59.   if(recipe.containsKey(s)){  
60.    int sum=0;  
61.    for(String t : recipe.get(s)){  
62.     sum+=dfs(t);  
63.    }  
64.    res=min(res, sum);  
65.   }  
66.   return res;  
67.  }  
68.   
69.  void debug(Object... os){  
70.   System.err.println(Arrays.deepToString(os));  
71.  }  
72.   
73.  void print(String s){  
74.   System.out.print(s);  
75.  }  
76.   
77.  void println(String s){  
78.   System.out.println(s);  
79.  }  
80.   
81.  public static void main(String[] args){  
82.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
83.   new Main().run();  
84.  }  
85. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 HashMap<String, Integer> val;
 HashMap<String, LinkedList<String>> recipe;
 String item;

 void run(){
  for(;;){
   val=new HashMap<String, Integer>();
   recipe=new HashMap<String, LinkedList<String>>();
   n=sc.nextInt();
   if(n==0){
    break;
   }
   for(int i=0; i<n; i++){
    String s=sc.next();
    int d=sc.nextInt();
    val.put(s, d);
   }
   m=sc.nextInt();
   for(int j=0; j<m; j++){
    String s=sc.next();
    int k=sc.nextInt();
    LinkedList<String> list=new LinkedList<String>();
    for(int i=0; i<k; i++){
     String t=sc.next();
     list.add(t);
    }
    recipe.put(s, list);
   }
   item=sc.next();
   solve();
  }
 }

 void solve(){
  println(dfs(item)+"");
 }

 int dfs(String s){
  int res=INF;
  if(val.containsKey(s)){
   res=min(res, val.get(s));
  }
  if(recipe.containsKey(s)){
   int sum=0;
   for(String t : recipe.get(s)){
    sum+=dfs(t);
   }
   res=min(res, sum);
  }
  return res;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}