Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-02-17 18:26:15.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:apm2.in, apm2.outSursăInfoarena Monthly 2012, Runda 1
AutorCosmin GheorgheAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Apm2

Glorioasa Republică Populară va beneficia de un nou sistem de drumuri! Comisia prezidenţială desemnată sa realizeze această glorioasa sarcină a finalizat planul lucrărilor, folosindu-se cu talent de hârtia şi creioanele puse la dispoziţie de Republică pentru fiecare cetăţean. După cum ştie toată lumea, Republica are N mari oraşe, iar acestea vor fi legate de M drumuri bidirecţionale, fiecare astfel de drum având asociat o anumită taxă necesară pentru parcurgerea sa. Fiind dedicaţi omului de rând, membrii comisiei au aflat şi un arbore parţial de cost minim asociat noii reţele de drumuri, sugerând astfel o serie de drumuri ieftine pe care cetăţeanul le poate folosi pentru a călători intre oricare două oraşe ale Republicii.

Însă Marele Lider are alte priorităţi. Marele Fiu este un mare fan al emisiunii Top Gear, iar Marele Lider doreşte ca noua reţea de drumuri să-i impresioneze pe realizatorii acesteia, în caz că aceştia vor decide să viziteze ţara noastră. Astfel, Marele Lider desenează Q noi drumuri pe planul reţelei, drumuri care, după înţelepciunea sa, străbat peisaje impresionante. Marele Lider ar dori ca cel puţin unul din aceste drumuri noi desenate să ajungă în construcţia finală. Dornici să îndeplinească dorinţa Luminatului Conducător, membrii comisiei se întreabă acum, pentru fiecare nou drum propus, care este cea mai mare taxă posibila pe care o pot asocia drumului respectiv astfel încât acesta să apară sigur în arborele parţial de cost minim al Republicii.

Date de intrare

Prima linie a fişierului de intrare apm2.in va conţine pe prima sa linie cele trei numere N, M, si Q.
Fiecare dintre următoarele M linii va descrie câte un drum prin trei numere întregi: X, Y, cele două oraşe legate de drumul respectiv şi T, taxa asociată acestuia.
Fiecare dintre următoarele Q linii va descrie câte un drum adăugat de Marele Lider, prin două numere, A şi B reprezentând cele două oraşe legate de drumul respectiv.

Date de ieşire

Fişierul de ieşire apm2.out va conţine Q linii. Pe a i-a linie se va afla răspunsul întrebarea 'Care este cea mai mare taxă pe care o putem asocia celei de a i-a muchii ipotetice astfel incât aceasta să se afle sigur în arborele parţial de cost minim al reţelei?'.

Restricţii

  • 2N10 000

Exemplu

apm2.inapm2.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?