Problem I
Rauður gegn bláum

Mynd í eigu Rooster Teeth, commons.wikimedia.org

Fyrirtæki þitt er að halda tölvuöryggisæfingu, þú ert í árasarliðinu, það er að segja rauða liðinu. Lið þitt er búið að komast yfir gögn sem gefa skipulag innra nets bláa liðsins. Einnig tókst einum liðsfélaga að komast inn í eina tölvu þessa innranets og breyta SSH stillingunum svo þú getir tengst beint inn í hana.

Nú er komið að þér að nota þetta til að tengjast tiltekinni tölvu á þessu innra neti þar sem lykilorðið sem ykkur vantar bíður. Til þess þarf að SSH-a sig milli tölva á innra netinu sem eru tengdar. Fyrir hverja slíka tengingu eru hins vegar einhverjar líkur á því að kerfið taki eftir óvenjulegri netumferð og lokar á SSH lotu þína. Þegar þetta gerist þarftu að tengjast upphaflegu tölvunni og byrja upp á nýtt.

Til að forðast það að þurfa byrja alveg upp á nýtt í hvert sinn geturðu breytt SSH stillingunum á tölvu svo hægt sé að SSH-a sig beint inn í hana ef SSH lotunni er lokað. Þetta tekur $B$ tímaeiningar. Það að SSH-a sig frá einni tölvu í aðra á innra netinu tekur $S$ tíma og það að SSH-a sig inn í innra net þeirra á tölvu með breyttar SSH stillingar tekur $R$ tímaeiningar.

Sem reikniritasérfræðingur liðsins er þá undir þér komið að finna leið til að komast yfir lykilorðið á sem stystum tíma. Það er háð slembni hvað það tekur langan tíma svo við viljum aðferðina sem hefur lægsta væntan tíma.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $1 \leq N, M \leq 5\, 000$ aðskilin með bili. $N$ gefur fjölda tölva á innra netinu og $M$ fjölda tenginga milli þeirra.

Næst kemur ein lína með þremur heiltölum $1 \leq B, S, R \leq 10^4$, aðskilin með bili, fastarnir í lýsingunni að ofan.

Næst koma $M$ línur, hver með þremur tölum $1 \leq x, y \leq N$ og $ 0 \leq p \leq 1$. Slík lína gefur þá að hægt sé að SSH-a frá tölvu númer $x$ á innra netinu yfir í tölvu númer $y$ á innra netinu með líkum $p$, og þá eru líkur $1 - p$ að SSH lotunni sé lokað. Ávallt gildir að $x, y$ séu ólíkar heiltölur og $p$ fleytitala með mest $6$ stafi eftir kommu.

Tölva númer $1$ er tölvan með breyttar SSH stillingar til að byrja með og tölva númer $N$ er tölvan með lykilorðið sem vantar að fá.

Úttak

Prentið vænta tímann að tengjast tölvu númer $N$ ef besta mögulega aðferð er notuð. Gera má ráð fyrir að þetta sé alltaf hægt og að vænti tíminn sé endanlegur. Svar telst rétt ef bein eða hlutfallsleg skekkja þess frá réttu svari sé mest $10^{-5}$.

Útskýring á sýnidæmum

Í fyrra sýnidæmi er bara ein tenging, og það eru helmingslíkur á að það takist að SSH-a sig þar í gegn. Ef þetta tekst þá kostar það tíma $100$ og við erum búin. En ef það tekst ekki þá þurfum við að endurtengjast, sem tekur tíma $1000$, og reyna aftur. Svo hver misheppnuð tilraun kostar auka $1100$ tíma. Að meðaltali misheppnast þetta einu sinni, svo svarið verður $1200$.

Í seinna sýnidæmi eru tvær leiðir að marki okkar og betra er að velja leiðina um tölvu $3$ og $4$. Við færum okkur í tölvu $3$, sem mistekst að meðaltali $0.25$ sinnum, svo það tekur $150$ tíma. Svo breytum við stillingunum á tölvu $3$ sem tekur $1000$ tíma. Næst reynum við að komast úr tölvu $3$ í $4$ sem mistekst að meðaltali $9$ sinnum. En við getum tengst tölvu $3$ beint ef hlutir mistakast, svo hver misheppnuð tilraun tekur aðeins $200$ auka tíma. Þar með tekur þetta $1900$ tíma að meðaltali. Til að komast á leiðarenda breytum við ekki stillingunum á tölvu $4$, við bara höldum áfram. Það mistekst að meðaltali $0.25$ sinnum, en ef það mistekst þurfum við að reyna komast í tölvu $4$ aftur. Það tekur að meðaltali $1900$, plús $100$ að tengjast tölvukerfinu aftur og $100$ að taka aðra tilraun að fara úr $4$ í $5$. Því tekur það að komast í tölvu $5$ frá tölvu $4$ að meðaltali $100 + 0.25 \cdot 2100 = 625$. Samtals tekur þetta þá $3675$ tíma.

2 1
10 100 1000
1 2 0.5

1200

5 5
1000 100 100
1 2 0.8
2 5 0.01
1 3 0.8
3 4 0.1
4 5 0.8

3675