Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-02-17 19:45:41.
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ă glorioasă 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 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, şi 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 încât aceasta să se afle sigur în arborele parţial de cost minim al reţelei?'.

Restricţii

  • 2N10 000
  • 1M100 000
  • 1Q1000
  • Se consideră că un drum apare sigur în APM, dacă acesta apare în toate APM-urile posibile.
  • Cele Q întrebări sunt independente unele de altele. Cu alte cuvinte, răspunsul pentru un anumit drum se calculează presupunând ca acesta este singurul drum adăugat celorlalte M deja existente.
  • Se garantează că se poate călători între oricare două oraşe folosind cele M drumuri iniţiale ale planului.

Exemplu

apm2.inapm2.out
4 3 2
1 2 7
1 3 2
1 4 1
2 3
3 4
6
1

Explicaţie

Dacă drumul între oraşele 2 şi 3 are taxa 6, suntem siguri că acesta se va afla în toţi arborii parţiali de cost minim posibili.
Dacă am fi ales taxa egală cu 7, ar fi existat cel puţin un arbore care nu conţine acest drum: (1 2), (1 3), (1 4).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?