Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | risipa.in, risipa.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Cătălin Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 1.3 sec | Limită de memorie | 524288 KB |
| Scorul tău | N/A | Dificultate |
  3
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Risipă
Ion și Maria merg în concediu la Paris. Parisul constă din n intersecții conectate prin m străzi cu sens unic. La fiecare intersecție i (1 ≤ i ≤ n) se află un magazin de suveniruri cu marfă în valoare de ci. Ion și Maria se cazează la un hotel din intersecția h.
Dimineața, Maria spune: „Ioane, eu mă duc la muzee. Spune-mi unde ieșim la cină și ne vedem acolo!”. Ion este îngrozit, pentru că știe ce înseamnă asta. Dacă alege pentru cină o intersecție i inaccesibilă de la hotel, atunci Maria va sta în cameră supărată. În schimb, dacă intersecția i este accesibilă, atunci Maria, pornind de la hotel, va colinda pe toate străzile, intrînd în toate magazinele de suveniruri pe care le întîlnește și cumpărînd toată marfa. Poate chiar să viziteze unele străzi și intersecții de mai multe ori (dar magazinele nu mai aduc altă marfă în afară de cea inițială). Maria va cheltui cît mai mult posibil, iar seara va veni la întîlnire.
Ion vă cere ajutorul. Pentru fiecare intersecție, aflați suma pe care o va cheltui Maria dacă Ion îi propune să se întîlnească în acea intersecție.
Date de intrare
Fișierul de intrare risipa.in conține pe prima linie numerele n, m și h. Următoarea linie conține valorile c1 c2 ... cn. Următoarele m linii conțin perechi u v cu semnificația că există o stradă cu sensul de la u spre v.
Date de ieșire
În fișierul de ieșire risipa.out afișați, pentru fiecare intersecție i (1 ≤ i ≤ n), pe cîte o linie separată, suma pe care o va cheltui Maria dacă cina este într-un restaurant din intersecția i. Dacă nu există niciun drum de la hotel la intersecția i, afișați 0.
Restricții
- 1 ≤ n ≤ 100.000
- 1 ≤ m ≤ 300.000
- 1 ≤ h, u, v ≤ n
- 1 ≤ ci ≤ 10.000 pentru orice 1 ≤ i ≤ n
- Nu există străzi de la o intersecție la ea însăși.
- Între orice intersecții u și v (u ≠ v) există cel mult o stradă în fiecare sens.
| subtask | puncte | restricții |
|---|---|---|
| 1 | 20 | n ≤ 1.000; m ≤ 10.000; harta este aciclică. |
| 2 | 20 | n ≤ 1.000; m ≤ 10.000 |
| 3 | 28 | Harta este aciclică. |
| 4 | 32 | Fără restricții suplimentare. |
Exemplu
| risipa.in | risipa.out |
|---|---|
| 7 8 1 5 3 2 3 4 1 4 4 2 4 6 1 7 2 3 3 7 1 2 3 4 5 4 |
5 13 13 13 0 14 17 |
Explicație
...
