Fişierul intrare/ieşire:alegeri.in, alegeri.outSursăONIS 2014, Runda 3
AutorDragos OpricaAdăugată deDraStiKDragos Oprica DraStiK
Timp execuţie pe test0.8 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Alegeri

Cum anul acesta sunt alegeri prezidentiale, mai marii tarii s-au hotarat sa repare cateva autostrazi din Tara Minunilor astfel incat sa se poata ajunga din orice oras in oricare alt oras, mergand numai pe autostrazi care nu sunt stricate. Avand la dispozitie lista cu autostrazi, precum si lista cu autostrazile stricate, voi trebuie sa ii spuneti Presedintelui care e suma minima de bani pe care trebuie sa o cheltuie ca sa multumeasca pe toata lumea si sa castige alegerile, stiind ca cele N orasele din Tara Minunilor sunt codificate cu numere naturale intre 1 si N.

Date de intrare

Fişierul de intrare alegeri.in contine pe prima linie T, reprezentand numarul de teste. Un test contine pe prima linie N si M reprezentand numarul de orase si respectiv numarul de autostrazi din Tara Minunilor. Pe urmatoarele M linii sunt descrise autostrazile, sub una din urmatoarele forme:

  • 0 a b - care semnifica ca exista o autostrada intre orasele a si b
  • 1 a b c - care semnifica ca intre a si b exista o autostrada a carui reparatie costa c lei.

Date de ieşire

În fişierul de ieşire alegeri.out se vor afisa T numere, reprezentand raspunsul pentru cele T teste. In caz ca nu exista nicio solutie pentru un test, se va afisa -1.

Restricţii

  • T = 7
  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000
  • Costul unui drum este un numar pozitiv si nu depaseste 5000
  • Atentie! Autostrazile sunt drumuri cu doua sensuri si minim doua benzi pe sens.

Exemplu

alegeri.inalegeri.out
2
2 1
1 1 2 10
2 2
0 1 2
1 1 2 10
10
0

Explicaţie

In primul exemplu in Tara Minunilor exista doar doua orase, si o autostrada stricata intre ele. Deci costul de reparare este 10. in al doilea exemplu exista o autostrada functionala si o autostrada stricata intre cele doua orase. Deci Presedintele nu trebuie sa aloce niciun ban, caci oamenii au pe unde circula, si sunt fericiti.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content