Diferente intre titluri:
Diferente intre continut:
h2. Date de intrare
Fişierul de intrare $harbingers.in$ ...
Fişierul de intrare $harbingers.in$ contine un numar natural $N$, numarul de orase din tinutul Moldovei. Pe fiecare din urmatoarele $N-1$ linii se afla 3 intregi $u v d$, separati de cate un spatiu, care descriu o poteca de lungime $d$ intre orasele numerotate cu $u$ si $v$. Urmeaza apoi alte $N-1$ perechi de intregi, cate o pereche pe linie. Perechea a $i$-a, $S{~i~} V{~i~}$, descrie caracteristicile mesagerului din orasul $(i+1)$: $S{~i~}$ este numarul de minute necesar mesagerului de a se pregati de calatorie, iar $V{~i~}$ este numarul de minute necesar mesagerului pentru a calatori un kilometru. Nu exista niciun mesager in capitala.
h2. Date de ieşire
În fişierul de ieşire $harbingers.out$ ...
În fişierul de ieşire $harbingers.out$ trebuie sa se afle exact $N-1$ intregi. Al $i$-lea numar reprezinta timpul minim, in minute, necesar pentru a trimite un mesaj de la orasul $(i+1)$ la capitala.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $0 ≤ S{~i~} ≤ 10^9^$
* $1 ≤ V{~i~} ≤ 10^9^$
* Lungimea oricarei poteci nu va depasi $10 000$
* Pentru 20% din teste, $N ≤ 2 500$
* Pentru 50% din teste, fiecare oras se va invecina cu cel multe alte 2 orase (graful potecilor va fi un graf linie)
h2. Exemplu
h3. Explicaţie
...
!< problema/harbingers?tree.jpg 70%!
Potecile si lungimile lor sunt prezentate in imaginea din stanga. Timpul necesar pentru pregatirea calatoriei si viteza mesagerilor sunt scrise intre paranteze.
Timpul minim pentru a trimite un mesaj de la orasul 5 la capitala este obtinut dupa cum urmeaza. Mesagerul din orasul 5 preia mesajul si paraseste orasul dupa 2 minute. Strabate o distanta de 4 kilometri in 120 de minute, inainte de a ajunge in orasul 2. Acolo lasa mesajul mesagerului din orasul respectiv. Acesta are nevoie de 26 de minute pentru a pregati calatoria si va merge pentru 180 de minute inainte sa ajunga la capitala.
Timpul total este deci $2 + 120 + 26 + 180 = 328$.
== include(page="template/taskfooter" task_id="harbingers") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
