Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-05-29 20:04:36.
Revizia anterioară   Revizia următoare  

 

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

Por Costel si cei N-1 prieteni ai sai porci s-au facut soferi de autobuz ca sa-si castige coceanul. Porcii si-au terminat tura pe ziua de azi si vor sa se intalneasca ca sa-si imparta cocenii (ce prieteni buni!). Ei traisec in Orasul Porcilor, un oras format din N statii de autobuze legate intre ele prin M strazi bidirectionale, de lungimi diferite. Cei N porci, impreuna cu cele N autobuze ale lor, se gasesc toti in oras. Initial al i-lea porc se gaseste in al i-lea autobuz in a i-a statie de autobuz din oras. Obiectivul vostru este sa aduceti toti cei N porci in acelasi autobuz (autobuzele din Orasul Porcilor folosesc fizica nucleara pentru a putea face ca oricati porci grasi sa incape intr-un singur autobuz).

Exista doua tipuri de operatii pe care le puteti efectua:
1. Drive b x y - Autobuzul b trece din statia x in statia y, cu conditia ca autobuzul b sa fie in statia x, sa existe cel putin un porc in acesta (care sa-l conduca) si sa existe o strada intre statiile x si y. Costul operatiei este lungimea strazii.
2. Move p x y - porcul p trece din autobuzul x in autobuzul y, cu conditia ca porcul p sa se afle in autobuzul x iar autobuzele x si y sa fie in aceeasi statie. Costul operatiei este 0.

Asa cum am spus mai sus, intr-un autobuz incap oricati porci. De asemenea, intr-o statie incap oricate autobuze.

Porcii, solidari fiind, vor sa minimizeze distanta totala parcursa de toti la un loc. In plus, deoarece toti porcii sunt grasi si nu au chef sa se miste, trebuie ca un porc sa nu schimbe autobuzul de mai multe de 25 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 statii, respective numarul de strazi. Pe urmatoarele M linii se vor afla cate trei numere intregi x, y si c cu semnificatia ca exista o strada intre statiile x si y cu lungimea 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 porcii 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
  • -109 taxa unei strazi ≤ 109
  • Cmin ≤ 2*109

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 primul test, porcii 2 si 3 se duc in statia 1 unde intra in autobuzul lui Por Costel cu un cost total de 2.
In al doilea test, porcii se strang in statia 1. Porcul 4 se duce in statia 2, se muta in autobuzul 2 si se duce impreuna cu porcul 2 in statia 1, porcul 3 se duce in statia 1. Si de data aceasta, Por Costel sta degeaba si asteapta. Costul total este de 1+1+1=3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?