mesaj3

Mesaj 3

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

Poveste si cerinta...

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 $a{~i~}$ si ajunge in orasul $b{~i~}$. Pentru a transmite mesajul in toate orasele de pe ruta sa, mesagerul $i$ $(1 ≤ i ≤ M)$ va primi $X{~i~}$ galbeni.
 
h2. 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?

h2. 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 $a{~i~} b{~i~} X{~i~}$, cu semnificatia "mesagerul $i$ parcurge ruta de la orasul $a{~i~}$ la orasul $b{~i~}$, fiind platit cu $X{~i~}$ galbeni".

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

h2. Restrictii

* $... ≤ ... ≤ ...$

* $2 < N < 11011$
* $0 < M < 110011$
* $0 < X{~i~} < 1111$, pentru orice $1 &le; i &le; M$
* $1 &le; a{~i~}, b{~i~} &le; N$, pentru orice $1 &le; i &le; M$
* Nu vor exista mai mult de $9$ mesageri care sa treaca prin acelasi oras.

h2. Exemplu
table(example). |_. mesaj3.in |_. mesaj3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

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

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

1899