Fişierul intrare/ieşire:mesaj3.in, mesaj3.outSursăLot Suceava 2007
AutorDan-Ionut FecheteAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.35 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mesaj 3

Pana nu demult, in Bucovina existau doar N orase conectate intre ele prin N - 1 sosele bidirectionale. Cu toate acestea, se putea ajunge din orice oras in orice alt oras mergand pe una sau mai multe sosele.

Cand Stefan trebuia sa faca un anunt important, el trimitea mesajul catre fiecare dintre cei M mesageri ai sai. Fiecare mesager, dupa primirea mesajului de la Stefan, pleaca sa transmita mesajul primit pe o ruta fixata. Mai exact, mesagerul i (1 ≤ i ≤ M) va transmite mesajul in toate orasele situate pe ruta care porneste din orasul ai si ajunge in orasul bi. Pentru a transmite mesajul in toate orasele de pe ruta sa, mesagerul i (1 ≤ i ≤ M) va primi Xi galbeni.

Cerinta

Care este numar minim de galbeni pe care Stefan trebuia sa-l plateasca pentru ca mesajul sau sa ajunga in toate cele N orase din Bucovina?

Date de intrare

Fisierul de intrare mesaj3.in contine pe prima linie numarul natural N, reprezentand numarul de orase din Bucovina. Urmatoarele N - 1 linii contin cate doua numere naturale distincte separate printr-un spatiu a b cu semnificatia "exista o sosea care conecteaza direct orasele a si b". Pe linia N + 1 este scris un numar natural M reprezentand numarul de mesageri. Pe urmatoarele M linii se afla informatii despre cei M mesageri. Pe cea de a i-a linie dintre cele M (1 ≤ i ≤ M) sunt scrise trei numere naturale separate prin cate un spatiu ai bi Xi, cu semnificatia "mesagerul i parcurge ruta de la orasul ai la orasul bi, fiind platit cu Xi galbeni".

Date de iesire

Fisierul de iesire mesaj3.out va contine o singura linie pe care va fi scris numarul minim de galbeni pe care trebuie sa-i plateasca Stefan, pentru ca mesajul sa fie transmis in toate cele N orase.

Restrictii

  • 2 < N < 11011
  • 0 < M < 110011
  • 0 < Xi < 1111, pentru orice 1 ≤ i ≤ M
  • 1 ≤ ai, bi ≤ N, pentru orice 1 ≤ i ≤ M
  • Nu vor exista mai mult de 9 mesageri care sa treaca prin acelasi oras.

Exemplu

mesaj3.inmesaj3.out
10
1 2
1 3
3 4
3 5
5 6
5 7
5 8
2 9
2 10
9
8 6 10
10 9 10
1 4 30
4 1 10
7 8 50
1 7 10
6 1 10
10 1 10
9 1 10
40

Explicatie

Suma minima necesara este de 40 de galbeni.
Sunt necesari 4 mesageri, cu rutele:

  • 8 6
  • 1 7
  • 4 1
  • 10 9

Exista si alte solutii, dar pentru acestea suma necesara este mai mare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content