Fişierul intrare/ieşire:tunel.in, tunel.outSursăpreONI 2008 Runda 1
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tunelul groazei

Miruna a reusit de curand sa mituiasca functionarii publici din Tara Minunilor si astfel a capatat dreptul de a construi mult visatul tunel al groazei in parcul de distractii. Miruna crede ca dupa ce se va deschide, tunelul va fi cea mai importanta atractie a parcului. El consta din mai multe drumuri intunecate, care se intalnesc uneori in puncte de intersectie. Se stie ca sunt N astfel de puncte de intersectie, si M drumuri intunecate care leaga 2 puncte de intersectie. Pentru fiecare drum, se cunoaste timpul necesar parcurgerii lui. Tunelul are 2 usi prin care se poate intra sau iesi afara. Acestea se afla in intersectiile numerotate cu 1 si cu N. Initial, curajosii care se vor avanta sa incerce tunelul, vor intra pe usa din intersectia 1, iar apoi aceasta usa se va inchide in urma lor. Apoi, pentru a iesi afara, trebuie sa gaseasca intersectia cu numarul N. O data ce au ajuns in intersectia N calatoria lor ia sfarsit, usa se deschide si sunt obligati sa paraseasca tunelul. Deoarece este intuneric, ei nu vad aproape nimic, iar atunci cand ajung intr-o intersectie, exista aceeasi probabilitate sa isi continue traseul pe oricare din drumurile care isi au unul din capete in intersectia respectiva. Deoarece este o fetita mica si lacoma, Miruna ar dori sa stie care este media tuturor timpilor necesari pentru a parcurge drumurile de la intersectia 1 la N. Astfel ar putea estima ce profit ar avea si cat de repede si-ar recupera banii investiti in functionarii publici.

Date de intrare

Pe prima linie a fisierului de intrare tunel.in se vor gasi 2 numere intregi N si M, avand semnificatia din enunt. Pe urmatoarele M linii se vor afla cate 3 numere A, B si C, semnificand faptul ca intre intersectiile A si B exista un drum bidirectional a carui traversare dureaza C minute.

Date de iesire

In fisierul de iesire tunel.out veti scrie un singur numar real care reprezinta timpul mediu de parcurgere a drumurilor de la intersectia 1 la N. Rezultatul se accepta cu o eroare de 0.001.

Restrictii si precizari

  • 2 ≤ N ≤ 255
  • N-1 ≤ M ≤ 100000
  • Timpul necesar traversarii oricarui drum este mai mic decat 1000.
  • Din intersectia 1 se poate ajunge in oricare alta.
  • Pot exista mai multe drumuri care sa lege aceleasi intersectii.

Exemplu

tunel.intunel.out
4 3
1 2 1
2 3 1
3 4 1
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content