rusuoaica

Rusuoaica

== include(page="template/taskheader" task_id="rusuoaica") ==

Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Aceasta trebuie sa proiecteze reteaua de metrou a tinutului iGorj. Se cunoaste faptul ca primaria din iGorj a construit deja N statii de metrou si a sapat M tuneluri. Totusi acestia nu au instalat sine de tren pe tunelurile sapate. De asemenea, din lipsa de fonduri, primaria nu a sapat suficiente tuneluri, astfel ca se stie ca exista cel putin doua statii de metrou care nu sunt conectate printr-un drum subteran.

Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Aceasta trebuie sa proiecteze reteaua de metrou a tinutului iGorj. Se cunoaste faptul ca primaria din iGorj a construit deja N statii de metrou si a sapat M tuneluri. Totusi acestia nu au instalat sine de tren pe tunelurile sapate. De asemenea, din lipsa de fonduri, e posibil ca primaria sa nu fi sapat suficiente tuneluri, astfel ca este posibil sa existe doua statii de metrou care nu sunt conectate printr-un drum subteran.

In proiectarea retelei de metrou, Rusoaica poate face urmatoarele decizii:

{*} sa amplaseze sine de tren pe un tunel deja existent, platind un cost aferent tunelului respectiv

{*} sa amplaseze sine de tren pe un tunel deja existent, platind costul aferent tunelului respectiv

 {*} sa construiasca un nou tunel cu sine intre 2 statii de metrou, platind costul A

{*} sa distruga o statie de metrou, platind costul B

{*} sa vanda un tunel deja sapat Societatii Culturale iGorjenesti, urmand sa fie transformat in muzeu subteran; se va incasa costul aferent tunelului respectiv

Este de la sine inteles ca eficienta retelei de transport conteaza mai putin decat costul de productie al acesteia. Rusuoaica trebuie astfel sa gaseasca costul minim de proiectare
al retelei astfel ca din oricare statie sa se poata ajunge in oricare alta statie folosind doar metroul.

Rusuoaica nu va sapa noi tuneluri intre doua statii intre care deja exista un tunel al carui cost aferent este mai mic sau egal decat A.
De asemenea, Rusuoaica va prioritiza cumpararea tunelurilor de cost mai mic sau egal decat A.
 
Rusuoaica trebuie astfel sa gaseasca costul minim de proiectare al retelei, astfel ca din oricare statie sa se poata ajunge in oricare alta statie folosind doar metroul. Costul poate fi, de altfel si negativ (tunelurile vandute vor aduce profit mai mare decat ce se va cheltui pentru finalizarea proiectului).

h2. Date de intrare

Fişierul de intrare $rusuoaica.in$ va contine pe prima linie 4 numere N, M, A si B (cu semnificatia din enunt), iar pe fiecare din urmatoarele M linii, 3 numere t1 si t2 reprezentand ca exista muchie de la nodul t1 la nodul t2 de cost t3.

Fişierul de intrare $rusuoaica.in$ va contine pe prima linie 3 numere N, M si A (cu semnificatia din enunt), iar pe fiecare din urmatoarele M linii, 3 numere t1, t2 si t3 reprezentand ca exista deja un tunel de la statia t1 la statia t2 de cost aferent t3.

h2. Date de ieşire

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$ ; $1 ≤ M ≤ 400.000$
* Atat A cat si costurile tunelurilor sunt numere naturale mai mici decat 200
* Pentru $30$ puncte $1 ≤ N ≤ 1.000$
* Pentru alte $20$ puncte, toate costurile tunelurilor sunt 0
* Se poate construi un tunel cu costul A intre 2 statii chiar daca este sapat deja unul
* Un tunel cu sine construit cu costul A nu se poate vinde dupa cumparare
* Toate tunelurile sunt bidirectionale

h2. Exemplu
table(example). |_. rusuoaica.in |_. rusuoaica.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 10 5
 2 1 7
 3 2 2
 4 2 4
 5 2 1
 5 4 2
 6 2 4
 6 4 8
 6 5 8
 7 3 5
 7 6 8
| -16

|
h3. Explicaţie

...

Rusuoaica va cumpara tunelurile (2, 3, 2), (2, 5, 1), (2, 6, 4), (4, 5, 2), (7, 3, 5) va vinde restul tunelurilor si va sapa un nou tunel intre (1, 2).

== include(page="template/taskfooter" task_id="rusuoaica") ==