Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | harbingers.in, harbingers.out | Sursă | CEOI 2009 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 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 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.
Determinati pentru fiecare oras in parte timpul minim necesar pentru a trimite un mesaj catre capitala.
Date de intrare
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, Si Vi, descrie caracteristicile mesagerului din orasul (i+1): Si este numarul de minute necesar mesagerului de a se pregati de calatorie, iar Vi este numarul de minute necesar mesagerului pentru a calatori un kilometru. Nu exista niciun mesager in capitala.
Date de ieşire
În fişierul de ieşire harbingers.out trebuie sa se afle exact N-1 intregi. Al i-lea
The output file harbingers.out should consist of exactly one line containing N-1 integers.
The ith number represents the minimum time, in minutes, required to send a message from the
(i+1)th town to the capital.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| harbingers.in | harbingers.out |
|---|---|
| 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 |
Explicaţie
...
