Joc cooperatiu P74845

Les competicions ja no estan de moda. El que es porta ara són els jocs cooperatius, en què els participants col·laboren per assolir un objectiu comú. Així, un grup de n amics s’inspira en el joc de la cadena, en què una fila de persones es diuen a cau d’orella un missatge M d’una punta a l’altra, amb l’objectiu que M no es corrompi pel camí. No obstant, per fer el joc més divertit, s’hi introdueix algun canvi:

Sigui x l’emissor inicial de M, i sigui y el receptor final. A cada ronda del joc, la persona ‍u que acaba de rebre M (o bé x, si és la primera ronda) ha d’escollir una altra persona v i transmetre-li M. Per a tot parell (u, v), es coneix la probabilitat p_uv de que la transmissió directa del missatge de u a v sigui correcta. Aquesta probabilitat és independent de la ronda. Un missatge corromput no es recupera mai. El joc acaba quan M arriba a y.

Jugant òptimament, quina és la probabilitat de que M es transmeti de x a y correctament?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’amics n i el nombre m de probabilitats p_uv que són estrictament positives. Segueixen m tripletes u, v, p_uv, on u ≠ v. Finalment, tenim x i y. Assumiu 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, i que cada parell de u i v apareix com a molt un cop a l’entrada. Els amics estan numerats entre 0 i n−1.

Sortida

Per cada cas, escriviu amb cinc dígits decimals la màxima probabilitat de que el missatge arribi correctament de x a y. Si és impossible, digueu-ho.

Pista

La solució esperada està basada en un algorisme fonamental sobre els grafs.