| Fișierul intrare/ieșire | bigbrother.in, bigbrother.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
|
| Timp de execuție pe test | 0.35 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Big Brother
În Londra anului 1984 există N obiective de interes. Aceste obiective sunt conectate între ele prin M cabluri bidirecționale de date. Fiecare cablu leagă două obiective și este deținut de unul dintre cei C furnizori de comunicații ai Londrei. Între oricare două obiective nu există două cabluri ale aceluiași furnizor, dar pot exista cabluri de la furnizori diferiți. Oricare două obiective sunt conectate prin cabluri, direct sau indirect.
Pentru prevenirea crimelor de gândire, Big Brother a instalat câte un tele-ecran în fiecare obiectiv. Acum, el dorește să conecteze toate tele-ecranele între ele folosind cablurile existente. Fiecare furnizor anunță prețul fix pe care îl cere pentru a-și pune la dispoziție întreaga infrastructură. Care este prețul minim pe care Big Brother trebuie să îl plătească pentru a putea conecta toate tele-ecranele?
Date de intrare
Fișierul de intrare bigbrother.in conține
- pe prima linie numerele N M C
- pe a doua linie C numere naturale reprezentând, în ordine, prețurile cerute de cei C furnizori
- pe următoarele M linii câte un triplet de numere x y z cu semnificația că există un cablu de date între x și y deținut de furnizorul z.
Date de ieșire
În fișierul de ieșire bigbrother.out se va tipări un singur număr, reprezentând prețul minim pe care trebuie să îl plătească Big Brother.
Restricții
- 1 ≤ N ≤ 1.000
- 1 ≤ M ≤ 100.000
- 1 ≤ C ≤ 15
- Obiectivele sunt numerotate de la 1 la N.
- Furnizorii sunt numerotați de la 1 la C.
- Prețul fiecărui furnizor nu va depăși 1.000.000.
Exemplu
| bigbrother.in | bigbrother.out | imagine |
|---|---|---|
| 6 19 4 4 5 3 10 1 4 1 2 5 1 2 6 1 5 6 1 2 3 1 1 2 2 1 5 2 1 4 2 2 5 2 2 4 2 4 5 2 1 2 3 3 5 3 3 6 3 1 2 4 2 3 4 3 6 4 6 5 4 5 4 4 |
7 |
 |
Explicație
Furnizorii 1 și 3 conectează toate obiectivele și au prețul 4 + 3 = 7. Nu există alt furnizor sau combinație de furnizori care să conecteze toate obiectivele cu un preț mai mic.
