Signal Strength

Time limit1sMemory limit128 MB

Summary

Find the maximum signal strength reaching switch N-1 from switch 0 through a switch network with gain or loss multipliers on nodes and edges.

Level: Medium5 of 10
Topics: Graph, DFS, Dynamic programming, Brute force
Solved: No attempts yet

Problem

Net Profits Incorporated has announced a new generation of network switching devices that support high-speed, instantly reconfigurable networks across long distances.

Each network is built from a new kind of switch. A switch watches several input lines, locks on to the strongest signal it receives, and forwards that signal to every output line connected to its output ports.

Because the connecting lines are long, signal loss is a major concern, and the switches themselves add further loss. To fight both, some switches carry amplifiers. To prevent destructive feedback, switches with amplifiers are never wired into a cycle in which their output could reach their own input, even indirectly.

Write a program that predicts the effective signal strength received at one point of a network when a signal is started at another point. You are given a network of $N$ switches ( $1 \le N \le 1000$ ), numbered from $0$ . Each switch has a multiplier telling how much weaker or stronger its output is than the strongest input reaching it. A switch without an amplifier multiplies the strength by a factor of at least $0.1$ . A switch with an amplifier may multiply the strength by a factor as large as $5.0$ .

You are also given the connecting lines. Each line has a multiplier describing how much weaker the signal is at the end of the line than when it entered; these line multipliers are at least $0.1$ and at most $1.0$ .

Input

The input contains one or more networks.

Each network starts with a line holding a single integer $N$ , the number of switches; the switches are numbered starting at $0$ . A non-positive value of $N$ marks the end of the input and is not itself a network.

The next $N$ lines describe the switches in order. Each line begins with a floating-point number, the strength multiplier of that switch, followed by an integer $k$ , the number of lines attached to that switch's output. Then come $k$ pairs of numbers, one per output line: the first value of a pair is the number of the switch that receives the line as an input, and the second value is a floating-point multiplier for the signal loss along that line.

Output

For each network, print one line

Network M: X

where $M$ is the network's number (starting at $1$ ) and $X$ is the signal strength at the output of switch $N-1$ when a signal of strength $1.0$ is applied to (all) inputs of switch $0$ . If no signal ever reaches the output of switch $N-1$ , then $X$ is $0$ . Print $X$ with two digits after the decimal point.

Examples3

Example 1

Input

4
1.0 2 1 0.75 2 0.98
1.25 1 3 0.9
0.75 1 3 0.5
0.9 0
6
1.0 2 1 0.9 2 0.9
0.95 2 2 0.7 3 0.6
0.95 1 4 0.8
1.0 1 4 0.4
1.25 1 5 1.0
1.1 0
0

Expected output

Network 1: 0.76
Network 2: 0.94

Example 2
Input
```
1
1.0 0
0
```
Expected output
```
Network 1: 1.00
```
Example 3
Input
```
2
1.0 1 1 0.5
1.0 0
0
```
Expected output
```
Network 1: 0.50
```