srevni

Srevni

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

==Include(page="template/taskheader" task_id="srevni")==

Poveste ...

==Include(page="template/badtests")==

h2. Cerinta

Pe planeta Srevni exista $N$ orase legate intre ele prin strazi cu sens unic. Orasele sunt identificate prin numere cuprinse intre $1$ si $N$. In fiecare din aceste orase se produce un aliment foarte hranitor. Pretul de vanzare al alimentelor poate fi diferit de la oras la oras. Pentru a reduce costurile, transportul alimentelor se realizeaza astfel: o masina de comanda care trebuie sa alimenteze orasul $i$ pleaca din orasul $i$ spre orasul din care trebuie sa aduca alimentele. In momentul cand ajunge la destinatie este incarcata si teleportata in orasul $i$. Intr-o zi, Regnos, conducatorul planetei, plictisindu-se, s-a gandit ca ar fi bine sa stie care este cel mai mic pret de achizitie al alimentului pentru fiecare oras al planetei.

...

h2. Date de intare

h2. Restrictii

In fisierul de intrare $srevni.in$ vom avea pe prima linie doua numere intregi $N$ si $M$. Pe linia urmaroate se vor afla $N$ numere naturale separate intre ele prin spatii, care reprezinta preturile alimentelor in fiecare dintre cele $N$ orase. Pe fiecare dintre urmatoarele $M$ linii se vor afla cate doua numere intregi, separate intre ele printr-un spatiu, $X$ si $Y$, cu semnificatia ca exista drum de la orasul $X$ catre orasul $Y$.

...
 
h2. Date de intrare

h2. Date de iesire

...

Fisierul de iesire $srevni.out$ va contine pe prima linie $N$ numere separate intre ele prin spatii, care reprezinta cele mai mici preturi de achizitie ale alimentelor pentru fiecare dintre cele $N$ orase.

h2. Date de iesire

h2. Restrictii si precizari

...

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* Preturile sunt numere naturale cuprinse intre $1$ si $1 000 000$

h2. Exemplu

| srevni.in | srevni.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. srevni.in|_. srevni.out|
|4 4
1 2 4 3
1 3
2 4
3 2
3 4
|1 2 2 3|
 
 
==Include(page="template/taskfooter" task_id="srevni")==
 

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

981