Diferente pentru problema/harbingers intre reviziile #2 si #10

Diferente intre titluri:

harbingers
Harbingers

Diferente intre continut:

== include(page="template/taskheader" task_id="harbingers") ==
Cu mult timp in urma, pe teritoriul Moldovei existau $N$ orase medievale, numerotate in mod unic cu numere intregi intre $1$ si $N$. Orasul numerotat cu $1$ era fortareata unde locuia regele si era considerata ca fiind capitala tinutului. Intre aceste orase existau $N-1$ strazi bidirectionale, fiecare strazi avand o lungime cunoscuta, exprimata in kilometri. Deoarece locuitorii tinutului erau oameni inteligenti, aceste drumuri erau construite astfel incat alegand oricare doua orase, exista un drum de a ajunge de la primul la al doilea urmand numai strazile existente.
Cu mult timp in urma, pe teritoriul Moldovei existau $N$ orase medievale, numerotate in mod unic cu numere intregi intre $1$ si $N$. Orasul numerotat cu $1$ era Cetatea de Scaun si era considerata capitala tinutului. Intre aceste orase existau $N-1$ poteci bidirectionale, fiecare poteca avand o lungime cunoscuta, exprimata in kilometri. Potecile erau construite astfel incat exista un drum unic intre oricare doua orase, fara a trece de doua ori prin acelasi oras (graful potecilor era un arbore).
Cand un oras era in pericol de a fi atacat, situatia trebuie de urgenta raportata la capitala.
Cand un oras era atacat, mesajul de urgenta trebuia trimis cat mai repede catre capitala. Mesajul era transportat de mesageri, existand cate un mesager in fiecare oras. Fiecare mesager era caracterizat de durata necesara pentru a incepe calatoria si de viteza sa constanta dupa plecare.
Mesajul dintr-un oras era intotdeauna transportat pe cel mai scurt drum spre capitala. Initial, mesagerul din orasul atacat prelua mesajul. In fiecare oras pe care il traversa, un mesager avea 2 posibilitati: fie mergea spre orasul urmator in drumul spre capitala, fie lasa mesajul la mesagerul din orasul in care se afla. Mesagerul care primea mesajul aplica acelasi procedeu ca mai sus. Pe parcurs, un mesaj putea fi carat de un numar oarecare de mesageri inainte sa ajunga la capitala.
The message from a town should have been transmitted to the capital on the shortest path. Firstly, the harbinger from the considered town took the message. If the harbinger carrying the message was in a town other than the destination, he had two options: either choose to go to the next town on the way to the capital, or leave the message to a harbinger from that town. The harbinger who received the message became responsible for sending it and he considered the same procedure as above. Thus, the message could have been carried by several harbingers until it arrived at the destination.
 
Because potential dangers should have been immediately reported, the king wanted to know what is the minimum time, in minutes, for each town, to send a message to the capital.
 
Determinati pentru fiecare oras in parte timpul minim necesar pentru a trimite un mesaj catre capitala.
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
table(example). |_. harbingers.in |_. harbingers.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
|206 321 542 328
|
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.