Cooperative game P74845

Statement

thehtml

Competitions are not in fashion anymore. What is fashionable now are cooperative games, where the participants collaborate to achieve a common goal. So, n friends get inspired by the chain game, in which an array of people whisper a message M in order from one extreme to the other one, trying that M gets not corrupted on the way. But, to make the game more fun, some changes are made:

Let x be the initial transmitter of M, and let y be the final receiver. At each step of the game, the person u that just got M (or x, if it is the first round) must choose another person v and transmit M to him or her. For every pair (u, v), we know the probability puv that the direct transmision of the message from u to v is correct. That probability is independent of the round. A corrupted message never gets recovered. The game ends when M reaches y.

Playing optimally, what is the probability that M gets correctly transmitted from x to y?

Input

Input consists of several cases. Every case begins with the number of friends n and the number of probabilities puv that are strictly positive. Follow m triplets u, v, puv, where uv. Finally, we have x and y. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, and that every pair of u and v appears at most once in the input. Friends are numbered between 0 and n−1.

Output

For every case, print with five digits after the decimal point the maximum probability that the message correctly reaches y from x. If it is impossible, tell so.

Hint

The expected solution is based upon a fundamental graph algorithm.

Public test cases
• Input

```6 8
1 0 0.02478
3 4 0.49787
3 1 0.00335
0 5 0.06737
0 2 0.76787
5 1 0.00045
4 1 0.93533
2 3 0.18315
3 5

2 1
0 1 1
1 0

1 0
0 0

3 4
2 0 0.75008
0 2 0.00004
0 1 0.01831
1 2 0.00091
0 2
```

Output

```0.00078
impossible
1.00000
0.00004
```
• Information
Author
Enric Rodríguez
Language
English
Translator