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 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.
Cand un oras era atacat, situatia trebuia raportata cand mai repede posibil la capitala. Mesajul era transportat de mesageri, existand cate un mesager in fiecare oras. Fiecare mesager era caracterizat de numarul durata necesara pentru a incepe calatoria si de viteza sa constanta (exprimata in minute pe kilometru) dupa plecare.
Mesajul dintr-un oras era intotdeauna transportat pe cea mai scurta cale (unica) spre capitala. Initial, mesagerul din orasul atacat cara mesajul. In fiecare oras pe care il traversa, un mesager avea 2 posibilitati: fie mergea spre orasul urmator spre capitala, fie lasa mesajul la mesagerul din orasul in care se afla. Noul mesager 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 ...
Date de ieşire
În fişierul de ieşire harbingers.out ...
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
...
