Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | drumetii.in, drumetii.out | Sursă | Algoritmiada 2013, Runda 4 |
| Autor | Andrei Grigorean | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Drumetii
N personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are N luminisuri legate intre ele prin cararui de diferite lungimi. Initial personajele sunt in luminisul 1. Stim ca oricare doua cararui nu se vor intersecta decat intr-un luminis, si ca numarul total de cararui va fi N-1. Fiecare dintre cele N personaje urmeaza urmatoarea strategie de vizitare a padurii: Din luminisul in care se afla acum, alege o cararuie pe care nu a parcurs-o in prealabil, si merge pe aceasta. Deasemenea, daca sunt mai multe personaje in acelasi luminis care vor sa mearga mai departe pe aceeasi cararuie, atunci vor merge ca grup - se vor deplasa pe respectiva cararuie cu viteza celui mai incet dintre ele (calul lui Harap-Alb este mai rapid decat Cenusareasa!). Definim energia magica a unui personaj ca fiind egala cu suma din distanta * viteza pentru fiecare cararuie parcursa de acel personaj. Personajele fantastice vor sa gasesti suma maxima a energiilor magice pe care o pot obtine parcurgand padurea. Daca esti vrednic sa rezolvi aceasta problema vei fi rasplatit cu placeri nebanuite...si 100p.
Date de intrare
Fişierul de intrare drumetii.in va contine pe prima linia numarul N reprezentand numarul de personaje fantastice. Pe a doua linie din input se vor gasi N numere V1,V2...VN reprezentand vitezele de deplasare ale celor N personaje. Pe fiecare dintre liniile de la 3 la 3+N-2 se va gasi cate o pereche de numere X,Y,L cu semnificatia ca exista o cararuie de la X la Y de lungime L.
Date de ieşire
În fişierul de ieşire drumetii.out trebuie sa afisati energia magica maxima ce poate fi obtinuta de cele N personaje.
Restricţii
- 1 ≤ N ≤ 20
- 1 ≤ L ≤ 100 000
- 1 ≤ Vi ≤ 1000
- Se garanteaza ca se poate ajunge din nodul 1 in orice alt nod al padurii.
- O muchie poate fi parcursa in ambele sensuri.
- Un personaj nu are voie sa astepte intre-un poiana. Cu alte cuvinte, cazul in care doua personaje sunt in acelasi nod si aleg ambele sa mearga pe aceeasi cararuie, primul personaj merge iar al doilea astepta si merge dupa acesta este invalid.
- Odata ce un personaj sau grup de personaje nu se mai poate deplasa pe o cararuie nevizitata, acest personaj sau grup se va opri.
Exemplu
| drumetii.in | drumetii.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
