Cooperative game P74845


Statement
 

pdf   zip

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
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++