Fişierul intrare/ieşire:	trenuri2.in, trenuri2.out	Sursă	Lot Alba Iulia 2010, Baraj 1
Autor	Tiberiu Savin	Adăugată de	Dragos-Alin Rotaru •mathboy
Timp execuţie pe test	0.8 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Trenuri2

Peste nouă mări şi nouă ţări, într-o mare împărăţie, prinţesa Alexandra s-a îndrăgostit foarte tare de Făt-Frumos, cel mai puternic şi mai viteaz bărbat. Din nefericire pentru ea, în urmă cu mulţi ani, în timpul unei lupte împotriva lui Gefghev tiranicul împarat din vremea aceea, lui Făt Frumos i-a scăzut foarte mult karma şi din această cauză nu mai are voie să se apropie de instituţiile publice. Astfel, de fiecare dată când cei doi vor să se întâlnească, Făt frumos îi trimite Alexandrei un bileţel printr-un porumbel călător. Pe bileţel, Făt Frumos scrie cea mai apropiată staţie de tren faţă de pădurea în care se ascunde acesta. Aşadar, Alexandra trebuie să se ducă la cea mai apropiată staţie de tren şi de acolo să ajungă în staţia indicată de Făt Frumos. Aici intervine mama Alexandrei care nu-şi va lăsa fata să îşi abandoneze responsabilitaţile princiare chiar atât de uşor. De fiecare dată când fata vrea să se întâlnească cu Făt Frumos, trebuie să-i spună mamei timpul exact pe care îl va face trenul din staţia de plecare până la staţia indicată de Făt Frumos. Alexandra cunoaşte foarte bine sistemul feroviar din împărăţie şi ştie următoarele:

• Între oricare două staţii există un drum unic care nu trece prin aceeaşi staţie de două ori.
• Pentru oricare două staţii unite direct printr-o linie de cale ferată, Alexandra cunoaşte distanţa dintre staţii şi viteza maximă cu care un tren poate circula pe această linie.

Cerinţă

Alexandra nu se simte în largul ei când trebuie să facă calcule, mai cu seamă că împaraţia este foarte mare şi calculele pot deveni destul de complicate. Din aceasta cauză vă roagă să faceţi un program care primeşte configuraţia sistemului feroviar şi răspunde unor întrebări de forma x y v, cu următoarea semnificaţie: “Cât timp îi va fi necesar unui tren care poate merge cu viteza maximă v, să ajungă din staţia x în staţia y ?”.

Date de intrare

Pe prima linie a fişierului de intrare trenuri.in se află două numere: N şi M, reprezentând numărul de staţii din sistemul feroviar, respectiv numărul de întrebări pe care le pune Alexandra. Pe următoarele N – 1 linii, se află câte 4 numere x y d v având semnificaţia că există o linie de cale ferată directă de la staţia x la staţia y de lungime d, care nu poate fi parcursă cu cu o viteză mai mare decât v. Următoarele M linii conţin câte trei numere: x y z, reprezentând întrebările puse de Alexandra, având semnificaţia descrisă în enunţ.

Date de ieşire

În fişierul trenuri.out se vor afla M numere, câte unul pe linie, reprezentând răspunsurile la întrebările Alexandrei cu o precizie de trei zecimale.

Restricţii

• 3 < N, M < 100 000
• Pentru 30% din teste M < 100
• Lungimea unui drum va fi un număr natural mai mic decât 100 000
• Viteza maximă pe care o poate atinge un tren este un număr natural mai mic sau egal decât 1000
• Pentru fiecare întrebare se ştie că trenul va merge pe drumul minim dintre staţia x şi staţia y
• Oricare tren merge cu minimul dintre viteza maximă pe care o poate atinge şi viteza maximă admisă pe linia de cale ferată pe care se află.
• Diferenţa maximă cu care rezultatul final poate varia faţă de cel corect este de 0,001

Exemplu

Explicaţie

Primul tren va parcurge drumul dintre staţia 1 şi statia 3 cu viteza 5, iar drumul de la statia 4 la statia 4 cu viteza 7. Astfel, timpul total va fi:  6/5 + 2/7 = 1.485714286

Cum se trimit solutii?