Fişierul intrare/ieşire:razboi.in, razboi.outSursăHappy Coding 2
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test1.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Razboiul lumilor

Tara A are N orase numerotate de la 1 la N. Aceste orase sunt conectate prin strazi bidirectionale in asa fel incat exista exact un singur drum intre orice pereche de orase. Deoarece tara A a fost atacata de tara B, tara A vrea sa pozitioneze intr-unul din orasele ei comandamentul armatei. Din motive defensive, comandamentul trebuie plasat in orasul cu proprietatea ca maximul distantei dintre orasul ales si oricare alt oras este minima (in cazul in care un oras oarecare este atacat, comandamentul trebuie sa ajunga acolo cat mai repede posibil; folosind proprietatea de mai sus se incearca minimizarea pagubelor in cazul cel mai defavorabil).

Cerinta

Gasiti toate orasele in care poate fi plasat comandamentul.

Data de intrare

Fisierul de intrare razboi.in contine pe prima linie numarul T de teste. Urmatoarele linii descriu cele T teste. Prima linie a fiecarui test contine numarul N, reprezentand numarul de orase din tara A. Urmatoarele N-1 linii contin descrierea unei strazi - trei numere intregi separate prin spatii: A, B, D. A si B reprezinta numarul oraselor conectate de acea strada iar D reprezinta lungimea strazii.

Date de iesire

Pentru fiecare test afisati in fisierul razboi.out urmatoarea linie: "Testul nr #XXX", unde XXX reprezinta numarul testului respectiv. Afisati apoi pe urmatoarele linii numarul oraselor in care ar putea fi plasat comandamentul. Aceste numere trebuie afisate in ordine crescatoare.

Restrictii

  • 1 ≤ N ≤ 16000
  • 1 ≤ D ≤ 10000
  • 1 ≤ T ≤ 20

Exemplu

razboi.inrazboi.out
3
5
1 2 1
1 3 2
1 4 3
4 5 4
2
1 2 19
3
1 2 1
2 3 1
Testul nr #1
4
Testul nr #2
1
2
Testul nr #3
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content