Diferente pentru problema/autobuze3 intre reviziile #13 si #40

Diferente intre titluri:

autobuze3
Autobuze3

Diferente intre continut:

== include(page="template/taskheader" task_id="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.
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 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.
$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. Initialsoferul i se afla in autobuzul i, in orasul i.
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 23 de ori.
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.
h2. 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$.
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$.
h2. Date de ieşire
h2. Restricţii
* Pentru toate testele de la evaluare T = 10
* 1 <= N <= 10^5
* 1 <= M <= 2*10^5
* 0 <= taxa unei autostrazi <= 10^9
* Cmin <= 2*10^9
* Pentru toate testele de la evaluare $T = 10$
* $1 &leq; N &leq; 2*10^5^$
* $1 &leq; M &leq; 4*10^5^$
* $0 &leq;$ taxa unei autostrazi $&leq; 10^9^$
* $Cmin &leq; 2*10^9^$
* Graful este conex!
h2. Exemplu
h3. 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$.
== include(page="template/taskfooter" task_id="autobuze3") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.