Fişierul intrare/ieşire:drumetii.in, drumetii.outSursăAlgoritmiada 2013, Runda 4
AutorAndrei GrigoreanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drumetii

N personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are P 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 P-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!). In cazul in care un personaj ajunge intr-un luminis din care nu poate iesi (nu exista cararui nevizitate), atunci acel personaj se va opri. Vom numi un astel de luminis luminis terminal. Stim ca in padure exista cel mult N luminisuri terminale. Definim energia magica a padurii ca fiind egala cu suma din distanta * viteza pentru fiecare cararuie (daca o cararuie nu va fi parcursa, aceasta suma va fi 0). Personajele fantastice vor sa gasesti energia magica maxima ce se poate obtine. 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 a treia linie din input se va afla numarul P. Pe fiecare dintre liniile de la 4 la 4+P-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.

Restricţii

  • 2 ≤ N ≤ 16
  • 1 ≤ P ≤ 500
  • 1 ≤ L ≤ 100 000
  • 1 ≤ Vi ≤ 1 000
  • 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.

Exemplu

drumetii.indrumetii.out
3
3 4 9
3
1 2 10
1 3 10
120
4
81 372 461 987
4
1 2 64270
1 3 56978
3 4 28202
89278530

Explicaţie

In primul exemplu, personajele 1 si 2 vor calatori impreuna spre poiana 2, iar personajul al treilea va calatori singur spre poiana 3. Primele doua personaje vor parcurge muchia (1,2) cu viteza 3, iar personajul 3 va parcurge muchia (1,3) cu viteza 9. Costul total va fi 3*10+9*10=120.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content