Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | autobuze3.in, autobuze3.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" |
| Autor | Mihai Nitu | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
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.in | autobuze3.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.
