Diferențe pentru problema/bigbrother între reviziile #2 si #8

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

Poveste și cerință...

Î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?

h2. Date de intrare

Fișierul de intrare $bigbrother.in$ ...

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$].

h2. Date de ieșire

În fișierul de ieșire $bigbrother.out$ ...

Î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.

h2. 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.

h2. Exemplu
table(example).

|_. bigbrother.in |_. bigbrother.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|

|_. 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
| !problema/bigbrother?bigbrother.png!
|

h3. 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.

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