import java.util.ArrayList; import java.util.Scanner; public class SignalStrength { private Scanner in = new Scanner(System.in); private int currentNetwork = 0; private ArrayList switches = new ArrayList<>(); private ArrayList visited = new ArrayList<>(); private class Switch { private ArrayList children; // store index nums of children private ArrayList paths; // store paths corresponding to children private double maxamp; private double value; private int index; private Switch() { maxamp = - 1; children = new ArrayList(); paths = new ArrayList(); } } public static void main(String[] args ) { SignalStrength s = new SignalStrength(); s.solve(); } private void solve() { // Switch s = new Switch(); // Switch t = new Switch(); // switches.add(s); // switches.add(t); // s.children.add(1); // s.paths.add(0.9); // s.value = 1.0; // t.value = 1.0; // // System.out.println(solve(s)); while (in.hasNext()) { readInput(); reset(); if (!switches.isEmpty()) { System.out.printf( "Network " + new Integer(currentNetwork).toString() + ": %.2f\n", solve(switches.get(0))); } } } private double solve(Switch root) { // TODO Auto-generated method stub if (root.index == switches.size() -1) { // got to the final node root.maxamp = root.value; return root.value; } if (root.children.isEmpty()) { return 0.0; // we hit a dead end } double max = 0; visited.add(root.index, true); for (int i=0; i< root.children.size(); i++) { int childIdx = root.children.get(i); //System.out.println("size " + new Integer(root.children.size()).toString()); //System.out.println(childIdx); if (switches.get(childIdx).maxamp < 0 && !visited.get(childIdx)) { // if maxamp has not been calculated solve(switches.get(childIdx)); } if (root.paths.get(i) * switches.get(childIdx).maxamp > max && !visited.get(childIdx)) max = root.paths.get(i) * switches.get(childIdx).maxamp; } visited.set(root.index, false); root.maxamp = root.value * max; return root.value * max; } private void readInput() { // in.nextInt(); // in.nextDouble(); // in.nextInt(); // in.nextInt(); // in.nextDouble(); // in.nextInt(); // in.nextDouble(); // System.out.println("done"); switches.clear(); currentNetwork += 1; int n = in.nextInt(); for (int i = 0; i < n; i++) { switches.add(new Switch()); visited.add(false); switches.get(i).value = in.nextDouble(); switches.get(i).index = i; //System.out.println(switches.get(i).value); int m = in.nextInt(); //System.out.println(m); for (int j = 0; j < m; j ++) { switches.get(i).children.add(in.nextInt()); //System.out.println(switches.get(i).children.get(j)); switches.get(i).paths.add(in.nextDouble()); //System.out.println(switches.get(i).paths.get(j)); } } } public void reset() { for (int i = 0; i < visited.size(); i++ ) { visited.set(i, false); } } }