Fişierul intrare/ieşire:autobuze3.in, autobuze3.outSursăConcursul National de Informatica "Adolescent Grigore Moisil"
AutorMihai NituAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Autobuze3

A venit vara, iar soferii de autobuz sunt in extaz deoarece multa lume o sa se duca in vacanta cu autobuzele acestora. Tara in care traiesc acestia este compusa din N orase conectate intre ele prin M autostrazi de mare viteza cum doar in Romania mai vezi. Si pentru ca se aseamana foarte mult cu cele din Romania fiecare autostrada are o taxa pe care trebuie sa o platesti daca vrei sa circuli pe ea.

Exista doua tipuri de operatii:
1. Drive b x y - Autobuzul b trece din orasul x in orasul y, cu conditia ca autobuzul b sa fie in orasul x, sa existe cel putin un sofer in acesta si sa existe o autostrada construita intre orasele x si y. Costul operatiei este taxa autostrazii.
2. Move s x y - Soferul s trece din autobuzul x in autobuzul y, cu conditia ca soferul s sa se afle in autobuzul x iar autobuzele x si y sa fie in acelasi oras. Costul operatiei este 0.

Intr-un oras pot fi oricate autobuze iar in oricare autobuz incap toti cei N soferi. Initial soferul i se afla in autobuzul i, in orasul i.

Pentru ca soferii vor sa isi puna la punct planul de a castiga cat mai multi bani pe vara aceasta, ei trebuie sa se stranga toti intr-un singur autobuz ca sa discute. Pentru ca ei nu vor sa plateasca prea mult acestia va roaga sa le spuneti costul minim ca toti soferii sa ajunga intr-un singur autobuz si o succesiune de operatii (1 si 2) astfel incat totii soferii sa ajunga in acelasi autobuz cu costul minim de mai sus, si, in plus, niciun sofer sa nu-si schimbe autobuzul mai mult de 25 de ori.

Date de intrare

Fisierul de intrare autobuze3.in va contine pe prima linie un numar intreg T, reprezentand numarul de teste. Pe prima linie a fiecarui test se vor afla doua numere intregi N si M care reprezinta numarul de orase, respective numarul de autostrazi. Pe urmatoarele M linii se vor afla cate trei numere intregi x, y si c cu semnificatia ca exista o autostrada intre orasele x si y cu taxa c.

Date de ieşire

Fisierul de iesire autobuze3.out va contine raspunsurile pentru cele T teste. Pe prima linie a fiecarui test se afla un numar intreg Cmin ce reprezinta costul minim ca toti soferii sa ajunga intr-un singur autobuz. Pe urmatoarele linii se vor afisa operatiile, cate una pe linie. La sfarsitul operatiilor veti afisa cuvantul "Gata" pe o linie noua.

Restricţii

  • Pentru toate testele de la evaluare T = 10
  • 1 ≤ N ≤ 2*105
  • 1 ≤ M ≤ 4*105
  • 0 ≤ taxa unei autostrazi ≤ 109
  • Cmin ≤ 2*109
  • Graful este conex!

Exemplu

autobuze3.inautobuze3.out
2
3 3
1 2 1
1 3 1
2 3 2
4 5
1 2 1
1 3 1
2 3 2
2 4 1
3 4 2
2
Drive 2 2 1
Drive 3 3 1
Move 2 2 1
Move 3 3 1
Gata
3
Drive 4 4 2
Drive 3 3 1
Move 4 4 2
Drive 2 2 1
Move 2 2 1
Move 4 2 1
Move 3 3 1
Gata

Explicaţie

In pimul test, soferii 2 si 3 se duc in orasul 1 cu un cost total de 2.
In al doilea test, soferii se strang in orasul 1. Soferul 4 se duce in orasul 2, se muta in autobuzul 2 si se duce impreuna cu soferul 2 in orasul 1, soferul 3 se duce in orasul 1. Costul total este de 1+1+1=3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?