Fişierul intrare/ieşire:bigbrother.in, bigbrother.outSursăad-hoc
AutorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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.inbigbrother.outimagine
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici