Ursul Vișă este noua victimă a câinelui Scubi. După ce i-a furat papucul Liviei, Scubi a decis să i-l fure și lui Vișă. Ursul nostru preferat este sătul de astfel de jocuri și va pleca să-și recupreze papucul însă înainte de a face asta, va studia în detaliu strategia sa. Grădina pensiunii “Lupul Dacic” poate fi reprezentată sub forma unui graf orientat cu $N$ noduri și $M$ arce. Pentru că acesta este pus pe șotii, Scubi a lăsat câte un papuc în fiecare din aceste noduri. Papucul din nodul $i$ are mărimea $L_i$. Pentru că se entuziasmează prea tare atunci când aude de grafuri, Ursul Vișă a uitat ce număr avea la papuc, însă știe că trebuie să aibă cel mai mare număr.
Pentru fiecare din cele $N$ noduri, considerându-le ca și punct de start, găsiți care este dimensiunea celui mai mare papuc la care poate ajunge Ursul Vișă.
Pe prima linie se găsesc numerele naturale $N$ și $M$, iar pe următoarea linie se găsesc $N$ numere naturale, reprezentând dimensiunile papucilor din fiecare nod. Pe următoarele $M$ linii se găsesc câte o pereche de noduri $x \ y$, semnificând că există un arc de la nodul $x$ la nodul $y$.
Pe prima linie se vor afișa $N$ numere naturale, al $i$-lea număr reprezentând dimensiunea maximă a unui papuc accesibil din nodul $i$.
Intrare
5 5 7 4 4 5 2 1 2 3 2 3 4 4 3 5 2
Ieșire
7 4 5 5 4
Din nodul $1$ putem ajunge în nodurile $\{1, 2\}$, cel mai mare papuc găsit în acestea are dimensiunea $7$.
Din nodul $2$ putem ajunge în nodurile $\{2\}$, cel mai mare papuc găsit în acestea are dimensiunea $4$.
Din nodul $3$ putem ajunge în nodurile $\{2, 3, 4\}$, cel mai mare papuc găsit în acestea are dimensiunea $5$.
Din nodul $4$ putem ajunge în nodurile $\{2, 3, 4\}$, cel mai mare papuc găsit în acestea are dimensiunea $5$.
Din nodul $5$ putem ajunge în nodurile $\{2, 5\}$, cel mai mare papuc găsit în acestea are dimensiunea $2$.
| Autor: | Bogdan-Ioan Popa |
| Publicat de: | popa.bogdannnn |
Tags:
Programare dinamică Grafuri