import java.io.File; import java.io.FileNotFoundException; import java.util.*; public class MidAt2008A { public static void main(String[] args) { boolean usingFile = false; Scanner in = new Scanner(System.in); if (usingFile) { File f = new File("data.txt"); try { in.close(); in = new Scanner(f); } catch (FileNotFoundException e) { e.printStackTrace(); } } MidAt2008A mySolver = new MidAt2008A(); int set = 1; while (true) { double ret = mySolver.go(in); if (ret == -1) break; String out = String.format("Network %d: %2.2f", set++, ret); System.out.println(out); } } double go(Scanner in) { memo = new HashMap(); int n = in.nextInt(); if (n == 0) return -1; double[] amps = new double[1000]; ArrayList> kidsList = new ArrayList>(); for (int i = 0; i < n; i++) kidsList.add(new HashMap()); for (int i = 0; i < n; i++) { amps[i] = in.nextDouble(); int k = in.nextInt(); for (int j = 0; j < k; j++) { int target = in.nextInt(); double stren = in.nextDouble(); kidsList.get(target).put(i, stren); } } double ret = recur(n - 1, amps, kidsList); return ret; } HashMap memo = new HashMap(); double recur(int ind, double[] amps, ArrayList> kidsList) { HashMap map = kidsList.get(ind); if (ind == 0) return amps[0]; if(memo.containsKey(ind)) return memo.get(ind); memo.put(ind, (double) -1); double max = 0; for (int i : map.keySet()) { double ret = recur(i, amps, kidsList) * map.get(i); if (ret > max) max = ret; } memo.put(ind, max * amps[ind]); //System.out.println(ind + ": " + max * amps[ind]); return max * amps[ind]; } }