Fişierul intrare/ieşire:srevni.in, srevni.outSursăBursele Agora 2006
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Srevni

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

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.

Date de intare

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.

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.

Restrictii si precizari

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

Exemplu

srevni.insrevni.out
4 4
1 2 4 3
1 3
2 4
3 2
3 4
1 2 2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content