Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rusuoaica.in, rusuoaica.out | Sursă | FMI No Stress 9 Warmup |
| Autor | Ioan Alexandru Tifui, Usurelu Florian Robert | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rusuoaica
Rusuoaica, mare arhitecta in devenire din Manchester, a primit o tema complicata pentru ea de la facultate asa ca, evident, va cere ajutorul. Vi se da un graf neconex cu N noduri si M muchii bidirectionale cu costuri (proiectul de drumuri in constructie din tinutul iGorj, sa zicem). De altfel, puteti aplica pe graful dat operatii de tip:
* 1: platiti costul unei muchie din cele M date
* 2: creati o noua muchie intre 2 noduri oarecare platind costul A
* 3: stergeti un nod oarecare platind costul B
Rusuoaica trebuie sa determine costul minim pentru ca oricare 2 dintre nodurile ramase dupa eventuala folosire a operatiei de tip 3, sa fie conectate de un drum. (cele M muchii date nu exista, trebuie achitate cu costul dat pentru a fi create)
Ajutati-o pe Rusuoaica si spuneti-i costul total minim cerut!
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.
Date de ieşire
În fişierul de ieşire rusuoaica.out se va afla pe prima linie un singur numar reprezentand costul cerut.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| rusuoaica.in | rusuoaica.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
